树状数组用于变化区间的动态维护进行 \(O(logn)\) 的插入和删除。
\(lowbit(x)\) 表示二进制表示中最低位的1代表的值称为最小位值,实际上就是二进制表示中最低位的1代表的值称为最小位值 二进制表示中最低位的1加上后面的0的值。
设树状数组\(c\), \(c_i\) 表示 ${\textstyle \sum_{i = i - lowbit(i) + 1}^{i}c[i]} $,每次修改操作只需要修改包含 \(i\) 的c, 复杂度为 \(O(logn)\)。每次查询操作,将分段拼起来,复杂度为 \(O(logn)\)。
void init() {
for (int i = 1; i <= n; i++) {
c[i] = a[i];
}
}
int lowbit(int x) {
return x & -x;
}
void add(int x, int y) {
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += y;
}
}
int sum(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
ans += c[i];
}
return ans;
}
当需要区间修改时,就需要差分了。
\(c\) 不再需要初始值,最后加上就行。
add(u, k), add(v + 1, -k);
cout << a[u] + sum(u) << '\n';
标签:树状,二进制,lowbit,复杂度,数组,logn
From: https://www.cnblogs.com/JiCanDuck/p/18389050