数据结构-子段和-O(log(n))实现区间求和的列表

在这里记录一个数据结构,子段和。

也就是说,维护一个类数组序列,但是性能是,读写某个位置的值以及查询某个区间的和都是 O(log(n)) 的复杂度。

注意,一般的数组读写都是 O(1) 的,但是求和的话需要 O(n)。

下面说清楚如何做到这个全 O(log(n)) 的性能。

先上一段代码(来自浙大ACM算法模板):

https://github.com/fish-ball/zju_lib/blob/master/结构/子段和.txt


// 求sum{[0..n-1]} // 维护和查询复杂度均为O(logn) // 用于动态求子段和,数组内容保存在sum.a[]中 // 可以改成其他数据类型 #include <string.h> #define lowbit(x) ((x)&((x)^((x)-1))) #define MAXN 10000 struct sum { int n; int a[MAXN]; int c[MAXN]; void init(int sz) { memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); n = sz; } void update(int i, int v) { v -= a[i]; a[i++] += v; while(i <= n) { c[i-1] += v; i += lowbit(i); }; } int query(int i) { i += 1; int ret = 0; while(i) { ret += c[i-1]; i ^= lowbit(i); } return ret; } };

ok,这段代码实在是太“精巧”了,以至于一眼根本看不出来个所以然来。

但是从接口上看,我们可以看到,支持两个基本操作(init 就不算了):

  • 一个是 update,也就是写某个位置的值;
  • 另一个 query,也就是读从 0 到某个位置的求和;

上述两个操作都是 O(log(n)) 的。

下面我们来讲解这个数据结构的内在原理

先给一段输出,说明原理:

int main() {

    int a[] = {0, 1, 2, 5, 3, 6, 0, 7, 2, 9, 1, 2, 4, 3, 6, 2, 5};

    sum s;
    s.init(20);
    for(int i = 0; i <= 16; ++i) {
        s.update(i, a[i]);
    }

    for(int i = 0; i <= 16; ++i) {
        printf("%d\t%d\t%d\t%d\t%d\n", i, (i^lowbit(i)), s.a[i], s.query(i), s.c[i]);
    }

    system("pause");

    return 0;
}

我们先看下表:

i bin(i) bin(j) j a[i] q(i) c[i]
0 000000 —— 0 0 0
1 000001 000000 0 1 1 1
2 000010 000000 0 2 3 3
3 000011 000010 2 5 8 5
4 000100 000000 0 3 11 11
5 000101 000100 4 6 17 14
6 000110 000100 4 0 17 14
7 000111 000110 6 7 24 7
8 001000 000000 0 2 26 26
9 001001 001000 8 9 35 9
10 001010 001000 8 1 36 10
11 001011 001010 10 2 38 2
12 001100 001000 8 4 42 16
13 001101 001100 12 3 45 3
14 001110 001100 12 6 51 9
15 001111 001110 14 2 53 2
16 010000 000000 0 5 58 58

j = parent(i) = i 二进制除去最低位的 1 之后剩余的值 = i ^ lowbit(i)) query(i) = c[i] + query(parent(i))

可以看见,对某个位置 i 取和值 query(i),会经历一个长度不超过 log(n) 的递归链。

于是,我们就可以很轻便地用 O(log(n)) 实现查询子段和以及取某单位值 a[i](其实也可以归约成长度为 1 的子段和)。

剩下的问题是如何写入?

假设我们要给位置在 i = 11 的元素加上 x = 3,我们现在来考虑这个问题:

11 = 001011

我们要考虑,现在我们改变了 i = 12 位置的值;

现在我们需要考虑,有哪些比 i 大的坐标位置 j,query(j) 跨越了 i,即满足:

parent(j) < i < j

也就是说:如果存在这样的 j,因为它比 i 大,因此 query(j) 也应该增加 x = 3;

但是因为 parent(j) < i,因此我们如果仅仅改变了 c[i],那么求 query(j) 的时候将不会有任何改变。

同时显然,因为 parent(j) < i,query(parent(j)) 不应该有任何改变。

考虑到 query(j) = c[j] + query(parent(j)),只能让 c[j] 加上 x。

如此,即可保证所有 j > i,满足 parent(j) < i 的,其 query(j) 都是正确的。

那么对于其他 j > i:

  • 如果 parent(j) = i,那么由于 query(i) 是准确的,不需要调整;
  • 如果 parent(j) = k > i,那么 k 同样可以递归直到 k > i 落入 parent(k) >= i 的合理区间,也不需要调整。

比较拗口,举个栗子:

i = 11 = 001011

j = 12 = 001100 -> 001000 = 8 < i (需 +x) j = 13 = 001101 -> 001100 = 12 > i j = 14 = 001110 -> 001100 = 12 > i j = 15 = 001111 -> 001110 = 14 > i j = 16 = 010000 -> 000000 = 0 < i (需 +x)

那么,如何找到所有这些比 i 大的,满足 query(j) 跨越 了 i 的所有 j 呢,就是我们最终要解决的问题。

先直接抛结论,再来证明:

首先这样的 j (j > i) 分两种,一种是 j = 2 ^ k 的形式的,很显然因为 parent(j) = 0,所以必然满足。

除此之外的 j,可以断定:parent(j) & i = parent(j)

例如 i = 110011,那么 j = 110100 的话,parent(j) = 110000 就满足这个情况。

所以我们可以编辑 i 的前缀,例如 i = 110010100101:

我们遍历前缀,在其后面连续的 0 中随机放入一个 1,只要结果比 i 大,这个就是我们要的 j 之一,遍历完整就结束了。

  • 100000000000 -> 由于哪里加 1 都比 i 小,因此不考虑
  • 110000000000 -> 111000000000, 110100000000,其余都比 i 小
  • 110010000000 -> 110011000000
  • 110010100000 -> 110010110000, 110010101000
  • 110010100100 -> 110010100110

所以这样找出来的 j 就有上方右侧这 6 个。

再稍为归纳一下,发现这样的枚举只需要对 i 迭代 i += lowbit(i) 即可逐个遍历!

这样就跟我们的示例代码(update 方法的迭代)完全一致了!

这个归纳需要证明吗?留给读者吧,很晚我要睡了!


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/07/accumulation-list.html【数据结构-子段和-O(log(n))实现区间求和的列表】

发表评论

电子邮件地址不会被公开。 必填项已用*标注