树状数组理论与实践

哔哩哔哩讲解视频
优秀题解

引入问题

给出一个长度为\(n\)的数组，完成以下两种操作：

1. 将第\(i\)个数加上\(k\)
2. 输出区间\([i,j]\)内每个数的和

朴素算法

单点修改：\(O(1)\)
区间查询：\(O(n)\)

使用树状数组

单点修改：\(O(log_2n)\)
区间查询：\(O(log_2n)\)

前置知识

\(lowbit()\)运算：非负整数\(x\)在二进制表示下最低位\(1\)及其后面的\(0\)构成的数值。

举例说明：
\(lowbit(12)=lowbit([1100]_2)=[100]_2=4\)
函数实现：

int lowbit(int x){
    return x & -x;
}

树状数组思想

树状数组的本质思想是使用树结构维护“前缀和”，从而把时间复杂度降为\(O(log_2n)\)。

• 每个结点t[x]保存以x为根的子树中叶结点值的和
• 每个结点覆盖的长度为lowbit(x)
• t[x]结点的父结点为t[x + lowbit(x)]
• 树的深度为\(log_2n+1\)

树状数组操作

• add(x, k)表示将序列中第x个数加上k。
  

以add(3, 5)为例：
在整棵树上维护这个值，需要一层一层向上找到父结点，并将这些结点上的t[x]值都加上k，这样保证计算区间和时的结果正确。时间复杂度为\(O(log_2n)\)。

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

• ask(x)表示将查询序列前x个数的和
  

以ask(7)为例：
查询这个点的前缀和，需要从这个点向左上找到上一个结点，将加上其结点的值。向左上找到上一个结点，只需要将下标 x -= lowbit(x)，例如 7 - lowbit(7) = 6。

int ask(int x){
    int sum = 0;
    for(int i = x; i; i -= lowbit(i))
        sum += t[i];
    return sum;
}