树状数组知识点整理一
引言
原始的树状数组，是一个支持单点加区间查的结构。
要在可以接受的复杂度范围内实现区间查 ((Theta(log n))) ，肯定不能遍历区间 ((Theta(n))) 。如果用分块暴力可以将复杂度变为 ((Theta(sqrt n))) 。要想让时间复杂度更低，我们需要更高效的利用已知信息。
首先，最终规划肯定需要考虑到数组每一个元素，即所有点的信息加起来，我们能推得原始数组的信息。
其次，对于任意的区间查询，通过最终规划分解，至多分成 (Theta(log n)) 个区间，对应每次查询复杂度为 (Theta(1)) 。
最后，最终规划要支持单点加，同时能在合理复杂度 (Theta(log n)) 时间内修改所有受到影响的点。
下面我们来看看原始的树状数组是如何通过规划满足上述条件的。
讨论
类比于前缀和的思想，我们让一个 原始数组 (a) 中的一些点从原来储存一位的值变成储存连续一段的和，记处理过的数组为 (c) 。
假设我们要查询 (a_s--a_t) 的和。
将任意查询区间划分为 (a_1--a_{s-1}) ，(a_1--a_t) 两部分，如果能分别得到两部分的区间和，那么相减就是查询区间的答案。
如果能保证每一段连续的长度都是 (2) 的幂，就可以根据下标将区间分为连续的子区间。
例如，如果要查询 (a_1) 到 (a_{111000_2} = a_{56_{10}}) 对应的区间和，按如下区间划分下标。
(110000_2--111000_2)，(100000_2--110000_2)，(0_2--100000_2)
即查询下述区间和
(a_{49}--a_{56})， (a_{33}--a_{48})， (a_1--a_{32})
相加即为所求。
这里我们考虑的区间为左开右闭。
如果按照上述要求，容易发现 (c_{1000000_2} = c_{64_{10}}) 中应该存储原始数组前64位的总和， (c_{100000_2} = c_{32_{10}}) 中应该存储原始数组前32位的总和。
那么中间的呢，例如 (c_{110000_2} = c_{48_{10}}) 中应该是什么？
显然，其中应该存储原始数组从32+1位到48位的总和。因为 (110000_2-100000_2 = 10000_2) ，即48位比32位要多出来16位，而正好16是2的幂。
同理能得到 (c_{110100_2} = c_{52_{10}}) 应该比48多出4位，所以 (c_{52_{10}}) 存储的就是从48+1位到52位的总和。
记 (k) 为数 (x) 在二进制下第一次出现1的位数对应的值 ((x=1100_2 Rightarrow k=100_2)) ，显然， (c_x) 存储的应该是从第 (x-k+1) 到第 (x) 位的总和。
为了快速得到 (k) ，于是有了函数 (lowbit()) 。
int lowbit(int x) { return x&-x; }
关于其原理，不再叙述。其结果就是数 (x) 对应的 (k) 。
有了这些，我们就能写出求区间1到x的和的代码。
int get_range(int x) {
int ans = 0;
while(x) {
ans += a[x];
x -= lowbit(x);
}
return ans;
}
即每次查询 (x-k+1) 到 (x) 的值，加到变量里，然后将 (x) 变为 (x-k) ，即去掉最后一个一。
显然，区间查询复杂度为 (Theta(log n)) 。
然后我们来考虑单点加的情况下，不妨设我们在 (c_{11010_2} = c_{26_{10}}) 的位置上加了一个数 。
显然，小于26的位置一定不会改变，第26位一定改变 。
考虑大于26位的情况。
容易发现，只有包含第26位也就是 (11010_2) 的区间会被更改。
考虑哪些区间包含 (11010_2) 。
由对于区间和的讨论可以知道任意数 (x) 代表的区间为 (x-lowbit(x)+1) 到 (x) 。
从小到大考虑，我们可以得到如下的值：
(11100_2, 100000_2, 1000000_2, ..., 100...00_2 leq n)
代码如下：
void add_point(int num, int loc) {
while(loc <= n) {
a[loc] += num;
loc = loc + lowbit(loc);
}
}
证明如下：
数 (X) 满足条件即指对于修改的点 (B) ，我们有 (X-lowbit(X) < B < X)
合理性：
假设 (loc) 满足题意，考虑 (loc+lowbit(loc) = c) 是否满足。
因为 (loc+lowbit(loc)) 一定会导致至少一位的进位，所以容易发现 (lowbit(loc)*2 leq lowbit(c)) 。
显然 (c-lowbit(c) leq loc-lowbit(loc)) 。
因为初始满足条件，由数学归纳法，证毕。
唯一性：
首先我们证明对于一个满足条件的数 (x) ，下一个满足条件的数一定是 (x+lowbit(x)) 。
考虑 (x+lowbit(y);lowbit(y)<lowbit(x)) 。
显然 (lowbit(y)) 对 (x) 的增值并不会造成进位，因为加的值小于 (x) 最小的1的位置对应的值。
那么我们有 (x+lowbit(y) - lowbit(x+lowbit(y))=x) 。
因为 (x) 满足条件，所以 (x) 大于给定的数，所以 (x+lowbit(y)) 不满足条件。
所以对于任意满足条件的数 (x) ， (x+1) 到 (x+lowbit(x)-1) 中不存在满足条件的数。
易得，仅有按上述规则得到的数满足条件。
证毕。
代码 （以洛谷P3374为例）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define ll long long
#define ull unsigned long long
#define cint const int&
#define Pi acos(-1)
const int mod = 998244353;
const int inf_int = 0x7fffffff;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;
int n, m;
ll a[500100];
int lowbit(cint x) { return x&-x; }
void add(cint num, int loc) {
while(loc <= n) {
a[loc] += num;
loc = loc + lowbit(loc);
}
}
ll get(int x, int y) {
ll ans = 0;
while(y) {
ans += a[y];
y -= lowbit(y);
}
while(x) {
ans -= a[x];
x -= lowbit(x);
}
return ans;
}
int main() {
cin >> n >> m;
int a;
for(int i=1; i<=n; i++) {
cin >> a;
add(a,i);
}
int b,c;
for(int i=1; i<=m; i++) {
cin >> a >> b >> c;
if(a==1) {
add(c, b);
} else {
cout << get(b-1, c) << endl;
}
}
return 0;
}
第二篇正在编辑中