树状数组

区间和

有一个区间问题如下：

  • 查询区间 \([l,r]\) 的和
  • 把 \(a_i\) 增加 \(x\)?。

可以使用树状数组来解决。

求 lowbit

我们定义 \(\text{lowbit}(x)\) 为 \(x\) 二进制表示中最右边 \(1\) 所对应的值。例如 \(6\) 的二进制为 \(110\)，那么 \(\text{lowbit}(6)=2\)，求 \(\text{lowbit}(40)=?\)

解析

先将 \(40\) 转化为二进制为 \(101000\)。其中倒数第 \(4\) 个的位权为 \(2^3=8\)，那么 \(\text{lowbit}(40)=8\)。

树状数组

lowbit

实际上求出 \(\text{lowbit}(x)\) 很方便，lowbit(x) = x & (-x)，这利用了计算机补码的性质，不需要理解。

树状数组

我们知道线段树的区间是安装中间点 \(mid\) 划分的，而树状数组是根据 \(\text{lowbit}\) 来划分区间的。

如下图表示 \(15\) 个结点的树状数组：

灰色的结点是树状数组中的结点，每一层结点的 \(\text{lowbit}\) 都是相等的。而每个灰色结点 \(i\) 和其前面的白色长条表示了结点 \(i\) 表示的区间。

查询

如果查询 \([l,r]\) 的和值，我们可以先求出 \([1,r]\) 的和值，然后减去 \([1,l-1]\) 的和值。那么现在的问题就是如何求 \([1,x]\) 上的和值。实际上很简单：

  1. 令 \(\text{sum}=0\)。
  2. 加上区间 \([x-\text{lowbit}(x)+1,x]\) 的和值。
  3. 令 \(x=x-\text{lowbit}(x)\)。
  4. 如果 \(x=0\) 则退出，否则重复步骤 1。

时间复杂度为 \(\mathcal{O}(\log x)\)???。

例如查询 \([1,11]\) 的和。

\(\text{sum}=C_{11}+C_{10}+C_{8}\)。

int getsum(int x) {
    int res = 0;
    for (int i = x;i > 0;i -= lowbit(i)) {
        res += C[i];
    }
    return res;
}

更新

如果让 \(a_x\) 增加 \(v\)，那么只有对于包含位置 \(x\) 的区间和值才会受到影响。

方法是每次都令 \(x=x+\text{lowbit}(x)\)，直到 \(x>n\)。

下图是修改 \(a_3\) 的值时的操作：

void update(int x, int v) {
    for (int i = x;i <= n;i += lowbit(i)) {
        C[i] += v;
    }
    return;
}

代码实现

#include 
using namespace std;
const int maxn = 110;
int C[maxn], n;
int lowbit(int x) {
    return x & (-x);
}
int getsum(int x) {
    int res = 0;
    for (int i = x;i > 0;i -= lowbit(i)) {
        res += C[i];
    }
    return res;
}
void update(int x, int v) {
    for (int i = x;i <= n;i += lowbit(i)) {
        C[i] += v;
    }
}
int main() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int v;
        cin >> v;
        update(i, v);
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << getsum(r) - getsum(l - 1) << endl;
    }
    return 0;    
}

相关

标签