Fenwick tree, binary indexed tree

参考

概要

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(int idx) {
    int ret = 0;
    for (int x = idx + 1; x > 0; x -= x&-x) {
      ret += ar[x];
    }
    return ret;
  }
};

Example

auto bit = BIT(10);
// 0 0 0 0

bit.add(0, 1);
// 1 0 0 0
cout << bit.sum(0) << endl; // 1
cout << bit.sum(1) << endl; // 1

bit.add(1, 1);
// 1 1 0 0
bit.add(3, 1);
// 1 1 0 1
cout << bit.sum(0) << endl; // 1
cout << bit.sum(1) << endl; // 2
cout << bit.sum(2) << endl; // 2
cout << bit.sum(3) << endl; // 3

bit.add(1, 1);
// 1 2 0 1
bit.add(2, -1);
// 1 2 -1 1
cout << bit.sum(0) << endl; // 1
cout << bit.sum(1) << endl; // 3
cout << bit.sum(2) << endl; // 2
cout << bit.sum(3) << endl; // 3

seq.bit.rs

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(&self, idx: usize) -> i32 {
        let mut sum = 0;
        let mut x = idx + 1;
        while x > 0 {
            sum += self.array[x];
            let xi = x as i32;
            x -= (xi&-xi) as usize;
        }
        sum
    }
}