树状数组正确性证明

极客资料网推荐树状数组正确性证明这篇文章给大家，欢迎收藏极客资料网享受知识的乐趣

（证明并不严谨，都是自己想的方法）

---

我将以下代码为后面证明过程中的树状数组模板

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

int query(int x){
    int res = 0;
    for(;x; x-= lowbit(x)){
        res += tree[x];
	}
    return res;
}

定义 \(A\) 为我们往树状数组（即tree数组）内加入的数的下标，\(B\) 为我们将要查询的下标 （\(A \ne 0\) 且 \(B \ne 0\)）

定义函数 \(P(x,y)\) 表示 x 自增 y 次 lowbit， 函数 \(M(x,y)\) 表示 x 自减 y 次 lowbit

我们要证明内容如下

• 当 \(A > B\) 时，满足 $\forall y_1,y_2 \ge 0 \(，\)P(A,y_1) \ne M(B,y_2)$

• 当 \(A \le B\) 时，恰好存在一组 \(y_1, y_2\) 满足 \(P(A, y_1) == M(B,y_2)\)

通俗的讲，就是保证在查询下标为 \(B\) 的前缀和时，加入的数中下标大于 \(B\) 的不会被计算，小于等于 \(B\) 的会被恰好计算一次

---

首先，我们需要发现一个性质，即在二进制下，一个数在自增 lowbit 时，当一位上的 0 变成 1 ，并满足其后面所有位置的数都是 0 ，且自增过程中会保证除首位外每一位 1 最后都会变成 0；相反的，一个数在自减 lowbit 中，当一位上的 1 变成 0 的，并满足其后面所有位置的数都是 0，且自减过程中会保每一位 1 最后都会变成 0

这里举一个例子，比如说对于一个二进制数字 1011000，其自增 lowbit 后会变成 1100000 ；会发现从右往左第 6 项变为了 0 ， 并且后面的数字也全都是 0

这个性质是显然可以证明的，故此不再证明

---

然后，我们证明最开始的内容

对于 \(A > B\) 的情况，因为 lowbit 不为负，所以始终满足 \(P(A, y_1) > M(B,y_2)\)

对于 \(A = B\) 的情况，又由于lowbit 必定为正，所以对于 $\forall y_1,y_2 \ge 1 $ ，满足 \(P(A, y_1) > M(B,y_2)\) ；且仅当 \(y_1 = 0\) 且 \(y_2 = 0\) 时 \(P(A, y_1) = P(B,y_2)\)

对于 \(A < B\) 的情况：

• 设 \(A = \sum_{i=0}^{n} a_i * 2^i (a_i \in \left \{ 0, 1\right \})\)， \(B = \sum_{i=0}^{n} b_i * 2^i (b_i \in \left \{ 0, 1\right \})\)

  即可以看成 \(A = {a_{n}a_{n-1}...a_2a_1a_0}_{(2)}\) ， \(B = {b_{n}b_{n-1}...b_2b_1b_0}_{(2)}\)

  则存在 \(j\) 满足 \(a_j < b_j\) 且 \(a_na_{n-1}...a_{j+1} = b_nb_{n-1}...b_{j+1}\)

  由于 \(a_j < b_j\) ，故此时 \(P(A,y_1) < M(B,y_2)\)，在 \(a_j = b_j\) 前一直成立

  此时又分两种情况

  • 当 \(a_ja_{j-1}...a_1a_0 = 0\) 时，由于上面性质可以得、到在自减 lowbit 时存在 \(y_2\) 使得 \(B = M(B,y_2)\) 后 \(b_j = 0\) 且 \(b_{j-1}b_{j-2}...b_1b_0 = 0\) ，所以此时 \(A = B\)， 即转变到了上一种情况
  • 当 \(a_ja_{j-1}...a_1a_0 > 0\) 时，由于上面性质可以得到在自加 lowbit 时存在 \(y_1\) 使得 \(A = P(A,y_1)\) 后 \(a_j = 1\) 且 \(a_{j-1}a_{j-2}...a_1a_0 = 0\) ，所以此时 \(A = B\)， 即转变到了上一种情况

故，证毕

文章来源:https://www.cnblogs.com/ac-wyr/p/19849065
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！