树状数组模板
class BIT {
vector<int> tree;
public:
BIT(int n) : tree(n) {}
// 将下标 i 上的数加一
void inc(int i) {
while (i < tree.size()) {
++tree[i];
i += i & -i;
}
}
// 返回闭区间 [1, i] 的元素和
int sum(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
// 返回闭区间 [left, right] 的元素和
int query(int left, int right) {
return sum(right) - sum(left - 1);
}
};