FenwickTree.cc

FenwickTree.cc

#include <iostream>
#include <vector>
//                8
//            /   \   \
//          4      6    7
//        /   \      \
//      2      3      5
//    /
//  1
class FenwickTree {
private:
  vector<int> arr;
  int lowbit(int x) { return x & (-x); }

public:
  FenwickTree(int n) : arr(vector<int>(n + 1)) {}

  int query(int i) {
    int sum = 0;
    while (i > 0) {
      sum += arr[i];
      i -= lowbit(i);
    }
    return sum;
  }

  void update(int i, int val) {
    while (i < arr.size()) {
      arr[i] += val;
      i += lowbit(i);
    }
  }
};