Fenwick tree, binary indexed tree

参考

概要

seq.bit.rs

use std::ops::Range;
struct BIT { size: usize, array: Vec<i32> }
impl BIT {
    fn new(n: usize) -> BIT {
        BIT  { size: n, array: vec![0; n + 1] }
    }
    fn add(&mut self, idx: usize, w: i32) {
        let mut x = idx + 1;
        while x <= self.size {
            self.array[x] += w;
            let xi = x as i32;
            x += (xi&-xi) as usize;
        }
    }
    fn sum_up(&self, idx: usize) -> i32 { // [0, idx)
        let mut sum = 0;
        let mut x = idx;
        while x > 0 {
            sum += self.array[x];
            let xi = x as i32;
            x -= (xi&-xi) as usize;
        }
        sum
    }
    fn sum(&self, range: Range<usize>) -> i32 {
        self.sum_up(range.end) - self.sum_up(range.start)
    }
}
fn main() {
    let mut bit = BIT::new(5);

    bit.add(0, 1);
    bit.add(4, 1);  // [1, 0, 0, 0, 1]
    trace!(bit.sum(0..0));  // 0
    trace!(bit.sum(0..1));  // 1
    trace!(bit.sum(0..2));  // 1
    trace!(bit.sum(0..3));  // 1
    trace!(bit.sum(0..4));  // 1
    trace!(bit.sum(0..5));  // 2
    trace!(bit.sum(1..4));  // 0
    trace!(bit.sum(1..5));  // 1
    trace!(bit.sum(2..5));  // 1

    bit.add(4, -1);
    bit.add(3, 1);
    bit.add(2, 2);  // [1, 0, 2, 1, 0]
    trace!(bit.sum(0..1));  // 1
    trace!(bit.sum(0..2));  // 1
    trace!(bit.sum(0..3));  // 3
    trace!(bit.sum(0..4));  // 4
    trace!(bit.sum(2..5));  // 3
}

seq.bit.cc

struct BIT {
  int N;
  int *ar;
  BIT(int n) {
    N = n;
    ar = new int[n+1];
    for(int i=0;i<n+1;ar[i++]=0);
  }
  ~BIT() {
    delete[] ar;
  }
  void add(int idx, int w) {
    for (int x = idx+1; x <= N; x += x&-x) {
      ar[x] += w;
    }
  }
  int sum_up(int idx) {
    int ret = 0;
    for (int x = idx; x > 0; x -= x&-x) {
      ret += ar[x];
    }
    return ret;
  }
  int sum(int left, int right) {  // [left, right)
      return sum_up(right) - sum_up(left);
  }
};
int main() {

    auto bit = BIT(5);

    bit.add(0, 1);
    bit.add(4, 1);  // [1, 0, 0, 0, 1]
    trace(bit.sum(0, 0));  // 0
    trace(bit.sum(0, 1));  // 1
    trace(bit.sum(0, 2));  // 1
    trace(bit.sum(0, 3));  // 1
    trace(bit.sum(0, 4));  // 1
    trace(bit.sum(0, 5));  // 2
    trace(bit.sum(1, 4));  // 0
    trace(bit.sum(1, 5));  // 1
    trace(bit.sum(2, 5));  // 1

    bit.add(4, -1);
    bit.add(3, 1);
    bit.add(2, 2);  // [1, 0, 2, 1, 0]
    trace(bit.sum(0, 1));  // 1
    trace(bit.sum(0, 2));  // 1
    trace(bit.sum(0, 3));  // 3
    trace(bit.sum(0, 4));  // 4
    trace(bit.sum(2, 5));  // 3

    return 0;
}