树状数组-JZTXT

树状数组用于变化区间的动态维护进行 $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';