现在的我，能成为你的女主角吗。——《路人女主的养成方法》

树状数组

树状数组的概念

树状数组（Binary Index Tree） 是一种时间复杂度为 的数据结构。

树状数组巧妙地利用了二进制。例如 ，转化为二进制数就是 ，如果我们要求前 项和，可以分别查询 、 以及 的和再相加。区间获取是一个不断地去掉二进制数最右边的一个1的过程。

我是BIT的过程！

我们定义，二进制数最右边的一个 ，连带着它之后的 为 （树状数组的核心）。那么我们用 维护区间 ，这样显然查询前 项和时需要合并的区间数是少于 的，树状数组的结构大概像下面这样：

我是树状数组！

树状数组的食用

单点修改

我个人比较喜欢 形式的：

1
2
3
4
5
6
7
8
9
10
inline void add (int x, int k)
{
	while (x <= n)
	{
		tree[x] += k;
		x += lowbit (x);
	}
    
	return ;
}

也可以写成 循环形式的：

1
2
3
4
5
6
7
inline void add (int x, int k)
{
	for (int i = x; i <= n; i += lowbit (x))
		tree[i] += k;
    
	return ;
}

求前缀和

这边也有 和 不同的写法，但是意思都是一样的

写法：

1
2
3
4
5
6
7
8
9
10
11
inline int query (int x)
{
	int ans = 0;
	while (x != 0)
	{
		ans += tree[x];
		x -= lowbit (x);
	}
    
	return ans;
}

循环写法：
1
2
3
4
5
6
7
8
inline int query (int x)
{
	int ans = 0; 
	for (int i = x; i; i -= lowbit (i))
		ans += tree[i];
    
	return ans;
}

区间修改

特殊的是，当我们求 的和时，需要用到前缀和思想。

具体代码这里就不贴了， 函数就是上面的板子。

1
2
add (x, k);
add (y + 1, -k);

这种方法很巧妙，先给 的每个数加 ，再给 的每个数加 。

那么当然也可以实现区间求和，就是利用前缀和优化上面“前 项和”的板子

树状数组在单点查询和单点修改上还是可以挥发出很大作用的（指码量），但是更推荐线段树，毕竟树状数组能做的事情，线段树都能做。

二维偏序

这是树状数组的一个拓展，至于我为什么不开新的文章是因为我想不出题目了（泪）。

然后因为老板想先看状压 所以我这边先咕了，各位加油，我暑假就更掉。