树状数组
查询操作:O(logn)
修改操作:O(logn)
#define lowbit(x) (x & -x) int tr[N]; // 树状数组 // 添加c个大小为x的数值 void add(int x, int c) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; } // 求数值大小在1~x的数值的和 int sum(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }