树状数组

树状数组是一种简洁优美的数据结构，能够高效维护动态前缀和，利用前缀和可以很快求出区间和。

问题引入：动态前缀和

【问题描述】

给定一个长度为 $n(\le 10^5)$ 的序列 $A[]$，可以进行 $Q(\le 10^5)$ 次操作:

• 修改: $A[i]$ 增加 $d$
• 询问: 询问前缀和 $S_i=A_1+A_2+\dots+A_i$

【分析】

如果暴力维护，每次询问都需要暴力求一次前缀和，总时间复杂度为 $O(nQ)$，那么如何优化？

优化策略很多，我们发现修改的时候，前缀和都需要重新计算，如果有多个管理员，每个管理员负责管理一段总和，那么修改的时候只需要修改部分管理员就可以了，这就是树状数组和后面分块思想基础，树状数组利用二进制优美的分段管理。接下来介绍树状数组如何非常优美的分段管理的。

以 $i=13$ 为例，任意一个整数都可以转换为二进制，$i=(13)_{10}=(1101)_2=(1000)_2+(100)_2+(1)_2$ .

那么前 $13$ 项可以分为长度为 $8+4+1$ 几个管理员管理，即 $[1,13]=[1,8]+[9,12]+[13,13]$ , 根据二进制，可以得到下面性质：

性质 $1$：按照二进制方式分组简单高效，区间 $[1,x]$ 可以分成 $O(\log{x})$ 级个小区间。证明

观察 $8=(1000)_2,12=(1100)_2,13=(1101)_2$, 我们发现管理员 $i$ 管理长度与 $i$ 在二进制下末尾 $0$ 的个数有关，二进制末尾 $0$ 的个数为 $k$，那么管理区间长度就是 $2^k$ 。

对于任意 $i$ 其管理区间长度为 $2^k$,其中 $k$ 为 $i$ 在二进制下 $0$ 的个数，记为 lowbit(i),后面再详细套路 lowbit(i) 求法。

即：设 $C[i]=a[i-2^k+1]+…+a[i]$, 其中 $k$ 为 $i$ 在二进制下末尾 $0$ 的个数, 令 $lowbit(i)=2^k$。

接下我们思考修改 $A[x]$ 的后果。

修改 $A[x]$ 后，那么所有覆盖 $A[x]$ 的管理员都要修改，第一级管理员是 $C[x]$ , 下一级管理员是 $C[x+lowbit(x)]$ .

例如：修改 $A[3]$, $x=3=(0011)_2$

• 第一级管理员 $C[3]$ ,管理范围是 $[3,3]$
• 上一级管理员 $C[3+lowbit(3)]=C[4]$, 管理范围是 $[1,4]$
• 上一级管理员 $C[4+lowbit(4)]=C[8]$, 管理范围是 $[1,8]$
• 上一级管理员 $C[8+lowbit(8)]=C[16]$, 管理范围是 $[1,16]$

性质 $2$ ：$C[x]$ 的上一级管理员是 $C[x+lowbit(x)]$

根据各自管理范围，可以得到如下树形结构：

从上下级管理关系角度，机构如下：

这样建立的结构就是树状数组，这种结构具有以下性质：

• $C[i]=A[i-lowbit(i)+1]+...+A[i]$
• 每个内部节点 $C[i]$ 的父节点(上一级管理员)是$C[i+lowbit(i)]$。（用于修改）
• $C[i]$ 前一个管理员是 $C[i-lowbit(i)]$ , 与 $C[i]$ 管理范围不重合，刚好衔接，可通过这种方式得到所有管理 $[1,i]$ 所有管理员。（用于查询前缀和）
• 对应树(森林)的深度是 $O(\log{N})$。如果 $N$ 不是 $2$ 的整次幂，那么树状数组就是一个具有同样性质的森林结构。

接下来思考 $lowbit(x)$ 求法？

lowbit

利用位运算，可以快速求出 $lowbit$ , 这是 $lowbit(x)$ 的几种求法：

lowbit(x)=x&(x^(x-1))=x&(~x+1)=x&(-x)

有了上述分析，我们在 $O(\log{n})$ 动态维护前缀和,能够动态维护前缀和，就能维护区间和。

查询前缀和

int C[N];    //树状数组 
int query(int x)  //查询前缀和 
{
	int ret=0;
	for(int i=x; i ; i-=i&(-i))
		ret+=C[i];   
	return ret; 
} 

可以利用前缀和作差求得区间和，区间 $[l,r]$ 和等于 query(r)-query(l-1)

单点修改

void add(int x,int d) //A[x] 增加 d 
{
	for(int i=x;i<=n;i+=i&(-i))
		C[i]+=d;	
} 

例1 P3374 【模板】树状数组 1

【题意简化】

给定一个长度为 $n(\le 5 \times 10^5)$ 序列 $A[]$，进行 $m(\le 5 \times 10^5)$ 次操作：给 $A[x]$ 加上一个值 $k$ , 或询问区间 $[l,r]$ 的区间和。

【分析】

典型的“单点修改、区间查询”，利用前缀和作差得到区间。直接用树状数组解决。

例2 P3368 【模板】树状数组 2

【题意简化】 给定一个长度为 $n(\le 5 \times 10^5)$ 序列 $A[]$，进行 $m(\le 5 \times 10^5)$ 次操作：给 $[l,r]$ 区间内每个数加上一个值 $k$ , 或询问 $A[x]$ 的值。

【分析】

如果用树状数组维护，将区间 $[l,r]$ 内每一个做单点修改，时间复杂度爆炸。

我们发现这个问题是“区间修改，单点询问” ，前面基础算法，知道“区间修改，相当于差分数组上单点修改”，“差分数组前缀和就是原数组”，具体参考前缀和与差分 。那么用树状数组维护差分数组，前缀和就是原数组单点的值。

• 区间 $[l,r]$ ,增加 $k$ . 相当于差分数组上 C[l]+=k,C[r+1]-=k
• 查询 A[x] 的值，就相当于询问差分数组前缀和

* P3372 【模板】线段树 1

操作包括：区间 $[l,r]$,增加 $k$ . 询问 $[l,r]$ 区间和 .

【分析】

对于“区间修改区间查询”问题可以使用“线段树”这种功能强大的数据结构维护，当然树状数组也可以，并且树状数组常数小代码量也小。

对于区间修改，显然还是转为差分数组维护，区间询问还是借助前缀和作差。

令 $C[i]=A[i]-A[i-1]$ ，当 $C[0]=0$ 时 , $A[i]=\sum_{j=1}^i{C[j]}$

那么 $A[i]$ 前缀和 $sum[i]$ 表示公式如下：

$sum[i]=A[1]+A[2]+...+A[i] = \sum_{j=1} ^1{C[j]} + \sum_{j=1}^2{C[j]}+ \dots +\sum_{j=1}^i{C[j]} $

展开以后

$sum[i]=i*C[1]+(i-1)*C[2]+...+C[i]$

$= \sum_{j=1}^i{(i-j+1)}*C[j]$

$=(i+1)*\sum_{j=1}^{i}C[j]-\sum_{j=1}^{i}{j*C[j]}$

需要同时维护 $C[j]$ 和 $j*C[j]$ 两个树状数组。

参考代码：点击

---

树状数组应用

1.逆序对

【题意简化】给定一个长度为 $n(\le 10^5)$ 个序列 $A[]$，问：序列中共有多少个逆序对？

$task1$: $1 \le A_i\le 10^5$

$task2$: $-10^9 \le A_i \le 10^9$

【分析】逆序对可以使用归并排序的方式求，也可以用树状数组。

以 $A_i$ 的值作为树状数组下标, 从大到小枚举 $A_i$ , 在 $A_i$ 位置上加 $1$, 此时在树状数组上 $[1,A_i-1]$ 位置存储的 $A[n]...A[i]$ 的信息，树状数组 $[1,A_i-1]$ 前缀和就是比 $A[i]$ 小的个数，也就是与 $A_i$ 形成逆序对的个数，将这个前缀和加入到答案中。

对于 $Subtask2$ 需要先进行离散化处理。

练习题：

P1908 逆序对

P1966 [NOIP 2013 提高组] 火柴排队

2.中位数

【题意简化】

给你 $Q$ 个操作：1. 在序列末尾增加一个数 $x$ ; 2. 询问当前中位数。

【分析】

可以采用“对顶堆”维护中位数，也可以“树状数组+二分”方式。

以 $x$ 的值作为树状数组下标，每增加一个数，就在 $x$ 位置处加 $1$ 。当前有 $p$ 个数，要查找中位数，我们发现树状数组前缀和是单调的，只需要找到第一个位置前缀和大于等于 $\frac{p}{2}$ , 树状数组下标位置就是中位数。

练习题：

P1168 中位数

P3369【模板】普通平衡树 (注：可以用“树状数组、线段树+二分”维护添加、删除、查询、前驱、后继等类似普通平衡树操作)

3. 树与树状数组

可以使用 $dfs$ 序将树转换为序列，一颗子树就对应 $dfs$ 序上的一段区间，那么很多树上问题就转化为区间问题了。

4. 树状数组优化DP

例 G0065. 套环【2025期中考试T5】

【题意简化】给定 $n$ 个矩形环, 询问最多选多少个能形成“大环套小环”(即 $w_i<w_j,h_i<h_j$) ,输出个数。

【分析】按照 $w$ 从小到大排序，就是在 $h$ 中查询最长上升子序列。可以用二分查询最长上升子序列，也可以树状数组或者线段树优化 LIS. 特别需要注意，排序的时候，当 $w$ 相等的时候，要按照 $h$ 从大到小排序。

---

学习完毕

{{ select(1) }}

• YES
• NO