树状数组
仅记录了树状数组一些操作。
参考https://oi-wiki.org/ds/fenwick/
操作Permalink
获取ci管理的数组a中的数的个数。
int lowbit(int x) {
return x & -x; //x + 1 = -x
}
单点修改Permalink
void add(int x, int v) {
while (x <= n) {
tr[x] += v;
x += bowbit(x);
}
}
单点查询Permalink
int getPrefix(int x) {
int ans = 0;
while (x) {
ans += tr[x];
x -= lowbit(x);
}
return ans;
}
区间修改Permalink
void update(int l, int r, int v) {
add(l, v); //l及之后的父节点都加上v
add(r + 1, -v); //(r + 1)及之后的父节点都减去v
}
区间查询Permalink
设b是维护序列a的差分数组，由差分数组的定义，有：ai=r∑i=1bi,
有以下推导： r∑i=1ai=r∑i=1i∑j=1bj=r∑i=1bi×(r−i+1)=r∑i=1bi×(r+1)−r∑i=1bi×i
int b[MAXN], ib[MAXN]; //上述两个的数组（差分数组和数组i*bi）
int getPrefix(int* nums, int x) {
int sum = 0, v = x + 1;
while (x) {
sum += v * b[x] - ib[x];
x -= lowbit(x);
}
return sum;
}
int getSum(int x) {
int ans = 0;
while (x) {
ans += getSum(nums, r) - getSum(nums, l - 1);
x -= bowbit(x);
}
return ans;
}
构造树Permalink
int tr[MAXN];
void initBIT() {
for (int i = 1; i <= n; i++) {
tr[i] += a[i]; //构造前缀和
b[i] += a[i] - a[i - 1]; //构造差分数组
int j = i + lowbit(i);
if (j <= n) tr[j] += tr[i];
}
}