树状数组

MarsTraveller · 2023-11-19 14:39:26 · 算法·理论

树状数组

树状数组是一个查询和修改复杂度都为 O(\log n) 的数据结构。其主要用途为数组的单点修改与区间求和，效率远远优于线段树。

一、基本思想

树状数组是一种基于二进制唯一分解性质的一种数据结构，其基本用途是维护序列前缀和，对于一个区间 [1,x]，树状数组将其分为 \log x 个小区间，从而快速询问区间和。

下面举一个例子：若数 x 的二进制表示为 (10101)_2，可以被分解成 2^4+2^2+2^0，所以我们可以将区间 [1,x] 分解成 O(\log n) 个区间：

1. 区间 [{\color{blue}1},{\color{red}2^4}]（长度 {\color{red}2^4}）。
2. 区间 [2^4+{\color{blue}1},2^4+{\color{red}2^2}] （长度 {\color{red}2^2}）。
3. 区间 [2^4+2^2+{\color{blue}1},2^4+2^2+{\color{red}2^0}]（长度 {\color{red}2^0}）。

二、基本算法

0. 前置：

我们将一个数的二进制分解后最小的那一个幂称为 \text{lowbit}(x)。

由上文标红可知，一个区间 [L,R] 的长度即为 \text{lowbit}(R)，所以此区间又可表示为 [R-\text{lowbit}(R)+1,R]。

所以，对于给定数组 A，我们可以建立数组 T，其中 ：

如图（C_i 即为 T_i）：

观察例图，发现树状数组有如下神奇的性质：

3. 树的深度为 O(\log n)。

这些性质是树状数组的精髓！

1. 单点修改（A_i += k）

根据树状数组的特性，对 A_i 进行操作以后，对于 A_i 的所有祖先节点 T_x 都需要进行维护，根据性质2，我们可以从 A_i 开始对该节点的父亲节点依次进行操作，总时间复杂度 O(\log n)。

void update(big id,big k)
{
    for(;id <= n;id += lowbit(id))
    {
        tree[id] += k;
    }
}

2. 区间查询（\sum_{i = l}^{r} A_i）

如下令：

我们可以得出区间 [1,i] 的和，通过两次查询相减的形式求出区间和。

如：\text{sum}[l,r] = \text{sum}[1,r] - \text{sum}[1,l-1]。

那么如何求出 \text{sum}[1,i] 呢？

根据性质1，我们通过从 i 开始，每次加上 T_i ，相当于加上了 \text{sum}[i-\text{lowbit}(i)+1,i]，下一次只需要计算 \text{sum}[1,i-\text{lowbit}(i)] 即可，所以 i = i-\text{lowbit}(i) 后，重复操作即可。

时间复杂度 O(\log n)。

big sum(big id)
{
    big ans = 0;
    for(;id >= 1;id -= lowbit(id))
    {
        ans += tree[id];
    }
    return ans;
}

单点修改 区间查询模板

例题：

1. P3374 【模板】树状数组 1。
2. P1908 逆序对。
3. The Battle of Chibi。

3. 区间修改：

设在 i 位置上的差分数组是 d_i。

考虑差分。将 区间 [x,y]的 每一个数都加 k，就相当于将 d_x +=