c++ implementation for date structure: binary indexed tree

binary_indexed_tree.cpp

struct BinaryIndexedTree {
    int up;
    long long tree[maxn];
    
    void init(int u) {
        up = u;
        memset(tree, 0, sizeof(tree));
    }
    
    inline int lowbit(int x) { return (x & (-x)); }
    
    void update(int pos, long long val) {
        while (pos <= up) { tree[pos] += val; pos += lowbit(pos); } 
    }
    
    long long calc(int pos) {
        long long ret = 0;
        while (pos) { ret += tree[pos]; pos -= lowbit(pos); }
        return ret;
    }
} biTree;  // init before any further operations, index starts from 1



// This version works for counting times of appearance
struct BIT {
  int sz;
  vector<int> num, sum;

  inline int lowbit(int x) {
    return x & -x;
  }  

  void add(int x) {
    num.push_back(x);
  }

  void init() {
    // to make index starts from 1, the number -1 should be smaller than any number in the vector
    num.push_back(-1);
    sort(num.begin(), num.end());
    sz = unique(num.begin(), num.end()) - num.begin() - 1;
    num.resize(sz + 1);
    sum.resize(sz + 1);
  }

  void update(int x, int d = 1) {
    int i = lower_bound(num.begin(), num.end(), x) - num.begin();
    while (i <= sz) {
      sum[i] += d;
      i += lowbit(i);
    }
  }

  int query(int x) {
    int i = upper_bound(num.begin(), num.end(), x) - num.begin() - 1;
    int ret = 0;
    while (i > 0) {
      ret += sum[i];
      i -= lowbit(i);
    }
    return ret;
  }
} bit[maxn];