树状数组——原理详解

前言

这两天在网上学树状数组，但是发现网上关于树状数组的解释大都对初学者不太友善，原理讲解部分并不是很容易理解，所以写了一篇树状数组，顺便帮自己巩固一下。

一、什么是树状数组

1.概念：

简单来说，这是一种数据结构。顾名思义，它通过树的结构来对数组进行高效操作，一般用于求数组前缀和以及区间和，并且可以在线维护数组，时间复杂度为\(O(logN)\)。

2.优点：

与ST表相比，树状数组有在线修改的功能；与线段树相比，树状数组的代码更简单。
当然，树状数组的局限性更大，此处不过多展开。

3.本质：

利用了二进制特性。

二、树状数组原理详解

先来看一张图：（可继续往下读，无须看懂）
图片来源于bilibili：〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

1.Lowbit

（1）定义

\(lowbit(x)\) 表示 \(x\) 在二进制下从右往左第一个 \(1\) 所代表的权值
例如：
\(lowbit(5_{10})=lowbit(101_2)=1_2=1_{10}\)
\(lowbit(12_{10})=lowbit(1100_2)=100_2=4_{10}\)

在十进制之下，\(lowbit(x)\) 表示的就是 \(x\) 以 \(2\) 为底指数最大的因数。当然，此处十进制意义不大。为了理解树状数组，我们只需要关注数字在二进制下的 \(lowbit()\) 即可，不需要关注十进制，也不需要关注二进制从右往左第一个 \(1\) 的左边是什么。

（2）Lowbit计算公式

公式如下：

\[lowbit(x)=x \&(-x) \]

① 机器码：原码、补码、反码

此处利用了计算机存储数字的特性。以 \(int\) 为例，一个 \(int\) 是 \(4\) 个字节，\(32\) 个比特。这 \(32\) 位中，最高位符号位，\(0\) 表示正数，\(1\) 表示负数。正数的存储即为其二进制（原码），负数的存储是其补码。
原码： 二进制表示
反码： 原码除符号位，其余各位取反
补码： 反码 \(+1\)

例如：
\(5\) 存储为 \(00000000\) \(00000000\) \(00000000\) \(00000101\)
\(-12\) 存储为 \(11111111\) \(11111111\) \(11111111\) \(11110100\)（补码）
（\(12\) 原码 \(00000000\) \(00000000\) \(00000000\) 00001100
反码 \(11111111\) \(11111111\) \(11111111\) \(11110011\)）

这样存储的意义是方便计算机利用符号位直接对机器数进行简单加法，从而完成减法运算，例如计算 \(5-12\) ，通过将二者机器数相加可以得到 \(11111111\) \(11111111\) \(11111111\) \(11111001\)， 即为 \(-7\) 的机器数。

② Lowbit 运算

以 \(12\) 为例：
\(12\) 与 \(-12\) 后八位编码分别为 $$00001100$$$$11110100$$
那么进行 \(\&\) 运算后就得到 \(000000100\)，即为 \(Lowbit(12)\)。

原理解释：
假设一个数 \(x\) 的编码是这样：\(\dots100\dots0\) ，加上负号 \(-x\) 即对原码取反再 \(+1\) ，取反变成 \(\dots011\dots1\)，\(+1\) 变成 \(\dots100\dots0\)，那么可以发现我们要求的 \(lowbit(x)\) 在 \(x\) 和 \(-x\) 中是一样的。
而更高位的数字由于取反，每一位都不同，那么 \(x\&(-x)\) 则可以得到后面的 \(lowbit(x)\) 部分。也就是说，任何一个 \(lowbit()\) ，取反再 \(+1\) 后一定为其本身。利用这个二进制特性，我们可以很方便地求得 \(lowbit()\)。

2.树状数组

（1）定义

（此处只是作者给出的定义，便于理解；网络上搜到的定义大多是描述性的，并没有明确的意思）

① 首先我们有一个数组 \(a[x]\) 用于存放原数列

② 树状数组是一个 \(int\) 型数组 \(tree[x]\)

③ 定义 \(tree[x]\) 表示以 \(a[x]\) 结尾，长度为 \(lowbit(x)\) 的一串数的和，即 \(tree[x]=\displaystyle\sum_{i=x-lowbit(x)+1}^{x}{a[i]}\)

（2）性质

我们将数组 \(a[x]\) 当做这棵树的叶节点，那么这棵树有以下性质：

性质① \(tree[x]\) 有 \(lowbit(x)\) 个子节点，其中一个为叶节点 \(a[x]\)

性质② \(tree[x]\) 的子节点为 \(tree[x-2^i] （i=0,1,2\dots(\log_2lowbit(x))-1）\) 和 \(a[x]\)

即 \(tree[x]=\displaystyle\sum_{i=0}^{(\log_2lowbit(x))-1}{tree[x-2^i]}+a[x]\)

性质③ \(tree[x]\) 的父节点为 \(tree[x+lowbit(x)]\)

结合下图理解三条性质：图片来源于bilibili：〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

（3）原理

首先最重要的是定义 \(tree[x]\) 表示以 \(a[x]\) 结尾，长度为 \(lowbit(x)\) 的一串数的和，即 \(tree[x]=\displaystyle\sum_{i=x-lowbit(x)+1}^{x}{a[i]}\)，以及树的递推关系 \(tree[x]=\displaystyle\sum_{i=0}^{(\log_2lowbit(x))-1}{tree[x-2^i]}+a[x]\)

下面以 \(tree[8]\) 为例：

① 长度规律理解

\(lowbit(8)=1000_2\)，即 \(tree[8]\) 表示长度为 \(1000_2\) 的一串数的和。
可以发现，二进制下，\(1000=0111+0001=(0100+0010+0001)+0001\)
其中 \(0111=0100+0010+0001\) 代表 \(tree[4]+tree[6]+tree[7]\)，长度分别为 \(4\)、\(2\)、\(1\)；\(0001\) 代表 \(a[8]\)，长度为 \(1\)
其长度之和 \(4+2+1+1=8=lowbit(8)\)（再次强调，仅需关注一个数的 \(lowbit()\) 即可）

二进制可以直观地看出其中的规律，而用我们熟悉的十进制来描述就是：\(2^n=\displaystyle\sum_{i=0}^{n-1}{2^i}+1\) （利用等比数列求和公式即可得到）。至此我们已经可以理解长度的规律。

② 子节点规律理解

那么如何得到这些子节点的编号呢？公式如下：\(son(x)=x-lowbit(2^i)=x-2^i(i=0,1,2\dots,(log_2lowbit(x))-1)\)
我们要求 \(tree[x]\) 的所有子节点 \(tree[i]\) 表示的长度 \(lowbit(i)\) 之和再 \(+1\) 等于 \(lowbit(x)\)。而对于任意一个 \(x\)，有 \(lowbit(x-2^i)=lowbit(2^i)=2^i(i=0,1,2\dots,(log_2lowbit(x))-1)\)（这样求得的子节点就符合要求了）。论证也很简单：考虑 \(x=\dots100\dots0,lowbit(x)=100\dots0\)，则有 \(x-lowbit(2^i)=(x-1)-lowbit(2^i)+1=\dots011\dots1-2^i+1=\dots011\dots1011\dots1+1=\dots011\dots1100\dots0\)，那么上面那个式子就可以得到直观的理解了。

我们已经从父节点推出子节点，那么显然，子节点 \(tree[x]\) 唯一的父节点即为 \(tree[x+lowbit(x)]\) 。

至此，我们已经完全理解了节点的定义以及节点间的递推关系，那么以数组为基础的树也就建好了。这就是树状数组。

三、树状数组应用

（注意，树状数组开原数组的一倍空间即可，由定义易证。）

1.单点修改，区间查询

（1）题目：【模板】树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 \(x\)

• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 \(n,m\)，分别表示该数列数字的个数和操作的总个数。

第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(m\) 行每行包含 \(3\) 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 \(x\) 个数加上 \(k\)

• 2 x y 含义：输出区间 \([x,y]\) 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 \(2\) 的结果。

（2）建树：

虽然上文提及我们需要用数组 \(a[x]\) 存储原数列，但实际上我们并不会真正调用 \(a[x]\)，因此我们输入时只要将第 \(i\) 个数存储在 \(tree[i]\) 即可，并以此为基础自底向上完成建树过程。
代码如下：

int lowbit(int x)
{return x&(-x);
}
void build()
{for(int i=1;i<=n;i++){int lb=lowbit(i);for(int j=1;j<lb;j<<=1)tree[i]+=tree[i-j];}
}

（3）单点修改：

自底向上逐个修改即可。
代码如下：

void add(int x,int k)
{for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;
}

（4）区间查询：

采用前缀和相减求区间和，只需依照定义循环求出 \(sum\) 即可。
代码如下：

int ask(int l,int r)
{int sum1=0,sum2=0;for(int i=r;i>=1;i-=lowbit(i)) sum1+=tree[i];for(int i=l-1;i>=1;i-=lowbit(i)) sum2+=tree[i];return sum1-sum2;
}

（5）完整代码：

#include<bits/stdc++.h>
using namespace std;
const int maxx=5*1e5+5;
int a[maxx],tree[maxx];
int n,m,cnt;int ans[maxx];
int lowbit(int x)
{return x&(-x);
}
void build()
{for(int i=1;i<=n;i++){int lb=lowbit(i);for(int j=1;j<lb;j<<=1)tree[i]+=tree[i-j];}
}
void add(int x,int k)
{for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;
}
int ask(int l,int r)
{int sum1=0,sum2=0;for(int i=r;i>=1;i-=lowbit(i)) sum1+=tree[i];for(int i=l-1;i>=1;i-=lowbit(i)) sum2+=tree[i];return sum1-sum2;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>tree[i];build();int t,x,y;for(int i=1;i<=m;i++){cin>>t>>x>>y;if(t==1) add(x,y);else ans[++cnt]=ask(x,y);}for(int i=1;i<=cnt;i++)cout<<ans[i]<<endl;return 0;
}

2.区间修改，单点查询

（1）题目：【模板】树状数组 2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 \(x\)；

2. 求出某一个数的值。

输入格式

第一行包含两个整数 \(N\)、\(M\)，分别表示该数列数字的个数和操作的总个数。

第二行包含 \(N\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 $i $ 项的初始值。

接下来 \(M\) 行每行包含 \(2\) 或 \(4\)个整数，表示一个操作，具体如下：

操作 \(1\)： 格式：1 x y k 含义：将区间 \([x,y]\) 内每个数加上 \(k\)；

操作 \(2\)： 格式：2 x 含义：输出第 \(x\) 个数的值。

输出格式

输出包含若干行整数，即为所有操作 \(2\) 的结果。

（2）差分数组及其性质

此题与上一题区别在于修改和查询的范围不同。区间修改可以理解为修改区间内每个单点，单点查询可以理解为查询长度为 \(1\) 的区间，那么用上一题的模板也可以解决。但这样完全是小题大做，并且算法显然会超时。因此，此题我们需要使用差分数组，并利用树状数组维护它。

什么是差分数组？

其核心在于作差：
现已知一个数列 \(a[x](a[0]=0)\)，定义 \(b[x]=a[x]-a[x-1](x\ge1)\)，\(b[x]\) 即差分数组，有以下性质：

性质① \(a[x]=\displaystyle\sum_{i=1}^{x}{b[i]}\) （简单的累加，证略）

性质② 当对一个区间进行加法修改时，对应的差分数组只有头尾改变。

如：对 \([l,r]\) 内每个数 \(a[l\dots r]+k\)，那么对应的差分数组操作则是： \(b[l]+k,b[r+1]-k\)

那么，接下来我们可以利用性质①进行单点查询，利用性质②进行区间修改。也就是利用差分数组将区间修改转化为单点修改，将单点查询转化为区间（和）查询。

（3）输入简化

虽然我们需要使用差分数组，但是我们不必求每一个数和其前一个数的差。我们只需记录每一次区间操作带来的差分数组的改变即可。其核心原理是：加法满足交换律。

证明：
如果未简化，那么操作如下：（暂时不考虑使用树状数组优化）

① 输入 \(a[x]\)，并求得 \(b[x]\)，\(b[x]=a[x]-a[x-1]\)

② 对区间 \([l,r]\) 进行加法操作 \(a[l\dots r]+=k\)，并修改：\(b[l]=b[l]+k，b[r+1]=b[r+1]-k\)

③ 查询 \(a[x]\)，\(a[x]=\displaystyle\sum_{i=1}^{x}{b[i]}\)

我们会发现，\(a[x]=\displaystyle\sum_{i=1}^{x}{b[i]}=\displaystyle\sum_{i=1}^{x}{(a[x]-a[x-1]+k_i)}=a[x]+\displaystyle\sum_{i=1}^{x}{k_i}\)，\(k_i\) 指对 \(b[i]\) 进行的操作。因此我们只需要记录 \(k_i\) 即可，这样可以简化代码。再以树状数组 \(tree[x]\) 辅助维护即可。

（4）完整代码

#include<bits/stdc++.h>
using namespace std;
const int maxx=5*1e5+5;
int arr[maxx],tree[maxx];
int ans[maxx],cnt;
int n,m;
int lowbit(int x)
{return x&(-x);
}
void add(int l,int r,int k)
{for(int i=l;i<=n;i+=lowbit(i))tree[i]+=k;for(int i=r+1;i<=n;i+=lowbit(i))tree[i]-=k;
}
int ask(int x)
{int tmp=0;for(int i=x;i>=1;i=i-lowbit(i))tmp+=tree[i];return arr[x]+tmp;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>arr[i];int t,x,y,k;for(int i=1;i<=m;i++){cin>>t;if(t==1){cin>>x>>y>>k;add(x,y,k);}else{cin>>x;ans[++cnt]=ask(x);}}for(int i=1;i<=cnt;i++)cout<<ans[i]<<endl;return 0;
}

后记

说真的，Fenwick真的太天才了，理解树状数组之后，我佩服的五体投地。实在是太巧妙了%%%%%%