【数据结构】树状数组

_GeorgeAAAADHD_ · 2024-07-19 08:38:54 · 个人记录

树状数组

Part 1. 定义与概念

那么我们可以建立一颗树状数组 c，位置 c_x 维护的是区间 [x-\operatorname{lowbit}(x)+1,x] 的信息。显然它长得像一颗树的结构。

Part 2. 操作

Part 2.1 单修区查（区修单查）

这里修改指加操作。

单点修改，显然只需修改所有管辖区间包含该位置的节点，即修改 c_x,c_{x+\operatorname{lowbit}(x)},\cdots,c_{\max \limits_{x\le n}x} 的值即可。
对应的前缀查询，则只需要访问 c_x,c_{x-\operatorname{lowbit}(x)},\cdots,c_{\min \limits_{x\ge 1}x} 的值即可，区间查询使用一个前缀和的思想即可完成。
区间查询，考虑将原数组 a_i 转为差分数组 d_i=a_i-a_{i-1}，那么查询区间 [1,r] 的和的式子就可以写为：

单点修改+区间查询代码：

#define lowbit(x) x&(-x)
struct BIT{
  int a[N];
  void add(int x,int k){while(x<=n)a[x]+=k,x+=lowbit(x);}
  int query(int x){int ans=0;while(x)ans+=a[x],x-=lowbit(x);return ans;}
  int range(int l,int r){if(l>r)return 0;return query(r)-query(l-1);}
}

如果是区间修改+单点查询，则可以用树状数组维护其差分数组。

Part 2.2 区修区查

我们对原数组 a_i 与其差分数组 d_i 进行研究，求区间 [l,r] 的和可以拆成求区间 [1,l-1] 与 [1,r] 的和，也就是：

&\sum\limits_{i=1}^ra_i \\=&\sum\limits_{i=1}^r\sum\limits_{j=1}^id_j \\=&\sum\limits_{i=1}^r d_i\times(r-i+1) \\=&(r+1)\times\sum\limits_{i=1}^r d_i-\sum\limits_{i=1}^r(d_i\times i) \end{aligned}

于是我们用两个树状数组分别维护 d_i 和 d_i\times i 即可。

据此，我们也可以推导其他运算，比如乘法，异或等。

如果要加的是一段等差数列呢？我们可以研究其二阶差分数组 d'_i，同样进行以下推导：

&\sum\limits_{i=1}^ra_i \\=&\sum\limits_{i=1}^r\sum\limits_{j=1}^id_j \\=&\sum\limits_{i=1}^r\sum\limits_{j=1}^i\sum\limits_{k=1}^j d'_k \\=&\sum\limits_{i=1}^r d'_i\times\dfrac{(r+i)\times (r-i+1)}{2} \\=&\dfrac{r^2+r}{2}\times \sum\limits_{i=1}^r d'_i+\dfrac{1}{2}\times\sum\limits_{i=1}^r d'_i\times i-\dfrac{1}{2}\times\sum\limits_{i=1}^r d'_i\times i^2 \end{aligned}

于是开三个树状数组，分别维护 d'_i,d'_i\times i,d'_i\times i^2 即可。

Part 2.3 二维树状数组

如果现在要维护一个矩阵呢？同样，令 a_{x,y} 维护从 (x-\operatorname{lowbit}(x)+1,y-\operatorname{lowbit}(y)+1) 到 (x,y) 的信息即可。

代码只需要对着一维的改一改就行了。

区修区查同理，只不过要维护四个东西了。

Part 3. 劣势

树状数组维护不可差分信息较难，且时间复杂度会多一个 \log。

模板见 \operatorname{loj} 130\sim135。

Part 4. 例题

其实很多时候都只是配合其他算法维护，这里选了一道树状数组专题。

P3221 双十字

定义双十字图形为以下格式：

两横一纵的 1，下面一横要严格长于上面一横
图形要沿纵轴轴对称
两横不能在相邻两行
纵轴顶端要高于上横，底端要低于下横

现在有一张 n\times m 的由 0 和 1 组成的图，其中有 k 个位置为 0，求该图双十子个数对 10^9+9 取模后的值。

先预处理每个点向上、向下分别可延展的最大格数，以及左右同时延展的最大格数。

我们考虑维护两个交点。具体地，维护上交点而枚举下交点。暂时不考虑上下延展的格数，设上交点左右延展最大格数为 x，下交点左右最大延展格数为 y。分类讨论：

若 x\ge y，当下交点延展格数为 i 时，上交点延展格数最大为 i-1，总情况数为 \dfrac{y(y-1)}{2}。
若 x<y，当下交点延展格数 i 超过 x+1 时，上交点延展格数最大为 x，否则为 i-1，总情况数为 x(y-x)+\dfrac{x(x-1)}{2}=xy-x^2+\dfrac{x(x-1)}{2}

于是枚举下端点，用四个树状数组分别维护 x=i 的上交点个数，x 之和，x^2 之和与 \dfrac{x(x-1)}{2} 之和即可。注意最后要乘以上交点向上延展格数与下交点向下延展格数。上交点延展格数在更新树状数组时直接乘进去即可。