前缀问题高效解法 – 树状数组详悉

综述

树状数组是解决 前缀 相关问题的一种数据结构
在前缀相关问题中可利用前序已计算结果避免重复计算降低复杂度
时间复杂度 $$\scriptsize O(log_2n)$$，可对相关问题进行算法优化

思想

对于 树状数组 $$\scriptsize bit[N]$$ 和 数据数组 $$\scriptsize a[N]$$
树状数组的每个节点表示 数据数组一个区间内所有节点的合计信息，如区间和、区间积等，其区间长度为 $$\scriptsize lowbit(x)$$。即 $$\scriptsize bit[x]$$ 表示 $$\scriptsize a(x- lowbit(x), x]$$ 区间中的合计信息

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

如，
节点 $$\scriptsize bit[3]$$ 区间长度为 $$\scriptsize lowbit(3) = 1$$，表示节点 $$\scriptsize bit[3] = a[3]$$
节点 $$\scriptsize bit[15]$$ 区间长度为 $$\scriptsize lowbit(15) = 1$$，表示节点 $$\scriptsize bit[15] = a[15]$$
节点 $$\scriptsize bit[6]$$ 区间长度为 $$\scriptsize lowbit(6) = 2$$，表示区间 $$\scriptsize a[5,6]$$ 的合计信息
节点 $$\scriptsize bit[16]$$ 区间长度为 $$\scriptsize lowbit(16) = 16$$，表示区间 $$\scriptsize a[1,16]$$ 的合计信息

由此大区间计算可分解为小区间信息的合计，分解步骤如下，
$$\scriptsize sum(a[1,i]) = sum(a[1，j]) + sum(a[j + 1, i]) = bit[i] + bit_{sub}[j],j = i - bit[i]区间长度$$
$$\scriptsize sum(a[1,i]) = sum(a[1，k]) + sum(a[k + 1, j]) = bit[j] + bit_{sub}[k],k = j - bit[j]区间长度$$
$$\scriptsize \cdots$$

将初始区间长度依次分解，结果为 2的最大幂次分解(各子区间长度是大区间二进制表示的各位十进制数)，如
$$\scriptsize sum(15) = bit(15) + bit(14) + bit(12) + bit(8) \\ = \sum_{i=15}^{15}a[i] + \sum_{i=13}^{14} + a[i] \sum_{i=9}^{12}a[i] + \sum_{i=1}^{8}a[i] \\ = 长度1 + 长度2 + 长度4 + 长度8$$，
$$\scriptsize sum(8) = bit(8) = \sum_{i=1}^{8}a[i] = 长度8$$，
$$\scriptsize sum(6) = bit(6) + bit(4) = \sum_{i=5}^{6}a[i] + \sum_{i=1}^{4}a[i] = 长度2 + 长度4$$，
$$\scriptsize sum(1) = bit(1)= \sum_{i=1}^{1}a[i] = 长度1$$

共分解 $$\scriptsize O(log_2n)$$ 次，也即计算 $$\scriptsize O(log_2n)$$ 次，构成由初始区间为父节点，各子区间为子节点的多叉树

实现和应用

前缀和

对于一列序列 $$\scriptsize a$$，求 $$\scriptsize suffix(m,n) = a[m] + a[m+1] + \dots + a[m+n]$$，其中$$\scriptsize suffix(m,n)$$ 是为以 $$\scriptsize a[m]$$ 为首的 前缀和

计算前缀和的三种方案
① 每次查询都从1累加到该数，无需考虑元素发生修改问题
② 边读入数据边累加，一次性计算出每个位置的前缀和并保存结果，查询时直接读取，任一元素发生修改重新计算后续所有前缀和
③ 构造树状数组，计算和时分解为小区间和，更新子区间时同时更新父区间

无需修改时首选 ②，N较大或涉及多次修改后再查询时，采用树状数组开销更小

const int N = 1000;
int bit[N + 1];

// 区间查询：分解计算区间和
int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= lowbit(i);
    }
    return s;
}

// 单点修改：运算过程中改动数据时修改父子区间和或初始化bit
void add(int i, int num) {
    while (i <= N) {
        bit[i] += num;
        i += lowbit(i);
    }
}

int main() {
    int a, ask;
    memset(bit, 0, sizeof(bit));
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a);
        add(i, a);
    }
    while (~scanf("%d", &ask))
        printf("%d", sum(ask));
    return 0;
}

区间和

区间 $$\scriptsize [i,j]$$ 的元素和 $$\scriptsize sum(a[1，j]) = suffix(1,j) - suffix(1,i-1)$$，即前缀和差值

...
int main() {
    ...
    while (~scanf("%d", &i, &j))
        printf("%d", sum(j) - sum(i - 1));
    return 0;
}

前缀最大值

构造树状数组时，所有区间都存储区间长度内的最大值
查询最大值时，依次向前序区间对比寻找最大值

const int N = 1000;
int bit[N + 1];

void add(int i, int num) {
    while(i <= N) {
        if(num > bit[i]) bit[i] = num;
        i += lowbit(i);
    }
}

int sum(int i) {
    int max = bit[i];
    while(i > 0) {
        i -= lowbit(i);
        if(i > 0 && max < bit[i])
            max = bit[i];
    }
    return max;
}

int main() {
    int a, ask;
    memset(bit, 0, sizeof(bit));
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a);
        add(i, a);
    }
    while (~scanf("%d", &ask))
        printf("%d", sum(ask));
    return 0;
}

逆序数

计算逆序数的三种方案
① 朴素方法，两层循环逐个向后扫描更小值，时间复杂度 $$\scriptsize O(N^2)$$，未利用任何已计算信息
② 归并排序，可利用归并时的两个有序子序列长度计算逆序数减少计算复杂度，时间复杂度 $$\scriptsize O(Nlog_2N)$$
③ 树状数组，利用前缀和思想，基于已计算区间结果来计算新的逆序数，时间复杂度 $$\scriptsize O(Nlog_2N)$$，详析如下

求解逆序数的几个关键
a）如何判断和统计逆序对数量：序列中某数与序列组成的逆序对数量等于 位于当前数后侧 且 小于当前数 的数字的数量
b）如何解决当前数后侧问题：若倒序读入序列，早先读入的数是后侧数，读入新数时后侧所有数均已读取完毕
c）如何统计小于当前数数量：若用一数组记录各数出现次数，则小于当前数 $$\scriptsize i$$ 的数字总数就是区间 $$\scriptsize [1,i-1]$$ 的 前缀和。因此以索引代表每个数，值代表该区间的内的数字计数来构建树状数组
*） 因此每读入一个数就向前求前缀和，实则检索该数后侧小于该数的个数。前缀和利用已计算结果因而降低了复杂度。每次求取完毕都更新读入数所在的树状数组区间计数。

例倒序读入序列 $$\scriptsize arr: 3,2,5,1,4$$，初始 $$\scriptsize bit: 0,0,0,0,0$$`
1）读入 $$\scriptsize 4$$，查询序列中 $$\scriptsize 4$$ 后侧 $$\scriptsize \lt4$$ 的数字数量，
即查询之前读入的其他 $$\scriptsize \lt4$$ 的数字数量，
即向前序 $$\scriptsize bit$$ 区间查询 $$\scriptsize sum(4-1)=bit(3)+bit(2)=0$$,
将计数更新到区间 $$\scriptsize bit(4) = 0 +1 = 1$$
$$\scriptsize bit: 0,0,0,0,0 \Rightarrow bit: 0,0,0,1,0$$
2）读入 $$\scriptsize 1$$，查询 $$\scriptsize sum(1-1)=bit(0)=0$$，没有 $$\scriptsize \lt1$$ 的数，
更新 $$\scriptsize 1$$ 所在的父子区间 $$\scriptsize bit(1)$$、$$\scriptsize bit(2)$$、$$\scriptsize bit(4)$$ 计数加一
$$\scriptsize bit: 0,0,0,1,0 \Rightarrow bit: 1,1,0,2,0$$
3）读入 $$\scriptsize 5$$，$$\scriptsize sum(5-1)=bit(4)=2$$,
$$\scriptsize bit: 1,1,0,2,0 \Rightarrow bit: 1,1,0,2,1$$
4）读入 $$\scriptsize 2$$，$$\scriptsize sum(2-1)=bit(1)=1$$,
$$\scriptsize bit: 1,1,0,2,1 \Rightarrow bit: 1,2,0,3,1$$
5）读入 $$\scriptsize 3$$，$$\scriptsize sum(3-1)=bit(2)=2$$,
$$\scriptsize bit: 1,2,0,3,1 \Rightarrow bit: 1,2,1,4,1$$
此时查询 $$\scriptsize sum(5)=bit(5)+bit(4)=1+4=5$$ 即为答案
由于其倒序读取的特殊性，处理完毕数的逆序数一定不会再发生变化，可在每次计算前缀和时即累加入结果

const int N = 100;
int bit[N], a[N];

void add(int i) {
    while(i <= N) {
        bit[i]++;
        i += lowbit(i);
    }
}

int sum(int i) {
    int s = 0;
    while(i > 0) {
        s += bit[i];
        i -= lowbit(i);
    }
    return s;
}

int main() {
    int ans = 0;
    memset(bit, 0, sizeof(bit));
    for(int i = 1; i <= N; i++)
        scanf("%d", &a[i]);

    for(int i = N; i > 0; i--) {
        ans += sum(a[i] - 1);
        add(a[i]);
    }

    printf("%d", ans);
    return 0;
}

二维前缀和

区间第k大值

lowbit为什么有效