树状数组模板

树状数组

初始化 Bit tr(n); // n 为树的长度
add(起点坐标, 增减数量);
sum(i坐标) // 计算前i的和。

code

// 树状数组
struct Bit {
  int n;
  vector<int> tr;
  Bit() {};
  Bit(int _n) { n = _n; tr.resize(n + 1); };

  void add(int a, int b) {
    while(a <= n) tr[a] += b, a += a & -a;
  }

  int sum(int a, int ret = 0) {
    while(a > 0) ret += tr[a], a -= a & -a;
    return ret;
  }
};