树状数组有什么用

原版博客传送门

这里以前缀和为例，树状数组一般用于以下情景：

进行很多次操作：

1.修改某个节点的值或查询某一个区间的和。（单点修改，区间查询）

2.某一个区间同时加上某个值或查询某个节点修改后的值。（区间修改，单点查询）

3.某一个区间同时加上某个值或查询某一个区间的和。（区间修改，区间查询）

树状数组代码简单，效率优秀，空间占用低。事实上，树状数组不止局限于求前缀和，也支持求某一个区间的最值、求逆序对等问题。树状数组的其他问题这里不进行讨论（太多了写不完），这里只以求前缀和为问题切入点。

前置知识：

1.lowbit函数

关于lowbit函数是什么，链接贴上了，这里不多讲。为什么要用lowbit待会儿讲。

关于lowbit函数_issey的博客-CSDN博客

2. 前缀和

直接用例子来说明吧：有一个数组 $a[10] = \left \{ 1,2,3,4,5,6,7,8,9,10 \right \}$

那么它的前缀数组 $sum[10] = \left \{ 1,3,6,10,15,21,28,36,45,55\right \}$ ,计算公式: $sum[i] = sum[i-1]+a[i]$ 。

通过这个数组，可以快速求得a数组区间[l,r]的和，计算公式: $sum_{l-r} = sum[r]-sum[l-1]$

第一种：单点修改，区间查询

这是最简单的一种，也是树状数组最基本的功能。

树状数组，就是将数组化为树的形式，通过层层“管理”来维护前缀和，图中C1~C8就是一个个"管理",所在层数就是"管辖层级"，它下面那些层中，和它直接或间接相连的节点就是它的"管辖节点",如果往上没有管理的节点，则称该节点为"最高级管理"。

（注：从别的博客拷贝的，侵权立删）

我们修改树状数组的单个节点值时，需要将他们上面的"管理"节点也依次更新，查询前缀和时，需要查询范围内每一个“最高级管理”节点保存的前缀和累加。一定要注意：更新数据和查询前缀和时依次经过的"管理"节点是不同的，（尽管公式上他俩差不多）

1.（单点更新）维护树状数组时经过节点的规则：下标每次加了个二进制的低位1（不知道啥是低位1的自行转lowbit）：

例如：（二进制）1 $\rightarrow$ 10 $\rightarrow$ 100 $\rightarrow$ 1000

(二进制) 1001 $\rightarrow$ 1010 $\rightarrow$ 1100 $\rightarrow$ 10000

(二进制)101 $\rightarrow$ 110 $\rightarrow$ 1000 $\rightarrow$ 10000

2. 查询前缀和经过节点的规则：下标每次减去一个二进制的低位1：

例如：（二进制）10000 $\rightarrow$ 0

(二进制)111111 $\rightarrow$ 111110 $\rightarrow$ 111100 $\rightarrow$ 111000 $\rightarrow$ 110000 $\rightarrow$ 100000 $\rightarrow$ 0

又比如，看图里的那根蓝色的箭头(下标用二进制表示)，意思就是要求 $A_{01} - A_{111}$ 的和, $sum = sum_{111}+sum_{110}+sum_{100}$

取低位1自然就是lowbit函数的作用。

再次说一下维护和查询的区别（以下下标均用二进制表示）

维护树状数组：意思是我们对某个节点加上（或减去）某个值后，它往上经过的节点均要更新。（它会影响往上沿路节点的值）

查询：查询 $1-i$ 节点的和，比如我们要查询 $1-111111$ 节点的和，把它依次减去最低位1的节点保存的前缀和加起来就是 $sum_{1-111111}$ ,即

$sum=sum_{111111}+sum_{111110}+sum_{111100}+sum_{111000}+sum_{110000}+sum_{100000}$

要注意查询时它在树中并不是"往下走"的，参考图中蓝色箭头，它的作用其实是把包括111111节点之前的各个"最高级管理员"保存的前缀和加起来。

好累，太难描述了。

接下来是 $[l,r]$ 区间查询，例如查询 $100-100000$ 节点的区间和，就是先求出 $1-100000$ 的区间和，再求出 $1-11$ 的区间和，然后两者相减即可。

$sum_{l-r} = sum[r]-sum[l-1]$

树状数组时间复杂度

单点修改：需要从底层往上依次更新节点，所以修改一次的复杂度为 $O(logn)$ ，对比普通数组修改节点值的时间复杂度： $O(n)$ 。

区间查询：依次加上减去低位1的节点值，时间复杂度 $O(logn)$ ,对比普通求前缀和的时间复杂度: $O(n)$ .

总体时间复杂度: $O(logn)$

单点修改，区间查询模板题

第一种的各个函数就不分开写了，树状数组的板子都大同小异，放一个单点更新，区间求和的板子题，本来打算放个模板上来，结果发现7个月之前能过，现在再交居然T了，（离谱），板子干脆放后面两种写吧，后面两种会包括第一种的板子。

题目链接：Problem - 1166 (dingbacode.com) 敌兵布阵

第二种：区间修改，单点查询

前置知识：差分数组

差分，即数据之间的差，差分数组，即数组中每相邻两个数据之间的差组成的数组。

例如：有一个数组 $A[10] = [2,2,3,3,4,5,6,9,9,7]$

那么A的差分数组 $B[10] = [2,0,1,0,1,1,1,3,0,-2]$ ,计算公式： $B[0] = A[0],B[i] = A[i]-A[i-1]$ .

那么B的前缀数组就是A数组对应的值。比如 $Bsum_{3} = A[3] = 3$ .

使用差分数组主要是为了区间修改，具体的说明可以去看这篇博客：

差分数组是个啥？能干啥？怎么用？（差分详解+例题）_From now on...的Blogs-CSDN博客_差分数组

了解了差分数组后，可以得到一个结论：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的**右端点的后一个值则会相反地变化**，而其他点的值保持不变。

正题

充分了解了第一种树状数组之后，我们可以得知，树状数组的单点更新是相对麻烦的，如果要将某一个区间统一加上某个值，采用第一种方式，一次更新的时间复杂度会是 $O(mlogn)$ ,（m为区间长度）。

但是如果我们用差分数组来进行操作：

每次更新维护差分的树状数组d，查询单点的值时，根据前置知识，差分数组的前i个值的和就是原数组第i个值，即：

$a_n = \sum_{i=1}^nd_i$

所以查询差分的树状数组d的前缀和 $sum_{i}$ ，就可以得到 $a_i$ 。我们就可以将每次更新区间的时间复杂度从 $O(mlogn)$ 降低至 $O(logn)$ .

单点查询（查询某个点的值）相对简单，那么紧接着是第三种：

第三种：区间更新，区间查询

思路继承第二种，都是利用了差分思想，区间更新的步骤一样，不过区间查询，查询的是某一个区间的和。

通过第二种，我们得知差分数组B的前缀数组就是原数据A数组对应的值。接下来我们要求A数组 $[l,r]$ 区间的和。又继承了第一种思路求 $[l,r]$ 区间和的部分思路，我们应该先求 $[1,r]$ 的和，再减去 $[1,l-1]$ 的和。

直接来一手公式，第三种用公式反而更容易理解：

设A为原数组，D为A的差分数组，则有：

$d_i = a_{i}-a_{i-1},d[0] =a[0]$

即，

$a_n = \sum_{i=1}^nd_i$

而A的前缀数组为: $\sum_{i=1}^xa_i$ ，带入公式得：

$\sum_{i=1}^xa_i = \sum_{i=1}^x\sum_{j=1}^id_i = \sum_{i=1}^x(x-i+1)d_i\\ =(x+1)\sum_{i=1}^xd_i-\sum_{i=1}^xid_i$

这样一来我们要求区间和，只需要维护两个树状数组：d的前缀数组和id的前缀数组就行了，然后通过上面这个公式就可以直接求出来a的前缀和。

接下来是区间修改，区间查询的各个部分的代码（其实也包括了前两种的代码，更新和查询原理都是一样的）

获取最低位1：

//获取最低位1
int lowbit(int x){return x&(-x);}

下面的代码中，d的前缀数组名称为differ，id的前缀数组名称为idiffer。

区间修改：

//该模块功能：在[l,r]区间同时加上某个值value
void update(int idex,int value,int n)
{
    int i = idex;
    while(idex<=n){
        differ[idex] += (ll)value;
        idiffer[idex] += (ll)value*i;
        idex += lowbit(idex);
    }
}

//注意，区间修改根据差分数组的规则，要修改两次：
update(l,value,n);
update(r+1,-value,n);

区间查询：

//该模块功能：获取[l,r]区间的前缀和
ll getSum(int idex)
{
    ll sum = 0;
    int x = idex;
    while(idex){
        sum += (x+1)*differ[idex];
        sum -= idiffer[idex];
        idex -= lowbit(idex);
    }
    return sum;
}

//查询[l,r]区间要先查[1,r]的和，减去[1,l-1]的和
sum += getSum(i,r);
sum -= getSum(i,l-1);

最后，分享一道区间修改，区间查询的模板题，题解代码完全可以作为模板代码。

题目链接：saikr oj | 二进制

题解链接： ADPC2 B二进制题解_issey的博客-CSDN博客

wlc的博客

博客

树状数组（单点修改，区间修改等）