树状数组

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