光与影的个人博客

NEUCoder

0%

树状数组整理

发表于 更新于 分类于 ，

树状数组（Binary indexed tree）

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

来自Wikipedia

树状数组是一种求解前缀和问题的简单数据结构，能够在O(logn)的时间复杂度内解决区间求和问题，主要支持两种操作

  1. 单点修改
  2. 区间操作

主要思路

类比任何数均可以拆分为有限个不同2的幂次的求和，原论文作者认为一串序列的求和同样可以拆分为有限个不同长度为2的幂次的序列的和。在数字的拆分中，其二进制表示中1的个数即为不同2的幂次，例如 “10”，“12”

自然想到一个问题：如何快速的找到任意数的不同二次幂的组合？引出了lowbit思路:

  1. 通过原码与补码求逻辑与运算，求得目标数字的最右边的一个1

  2. 原数字减去lowbit，获得少了一位1的数字

  3. 重复操作，直到 $x_i = 0$

重复此过程每一步计算得到的 $lowbit(x_i)$ 即为原数字的不同2的幂次拆分，以14为例:

如何将对应拆分思路迁移到前缀和？

不妨用 $C[i]$ 表示 目标数组$f[1]…f[i]$的前缀和，通过$lowerbit$操作，我们可以快速找到任意区间长度 对应的二次幂区间长度的组合。

问题是我们如何设计存储方式，提前存储这些二次幂区间长度的区间和？观察14转化为组合的过程，对应到区间表达形式为:

可以得到每个区间右边界可以由上个区间右边界减去lobit得到，而区间的长度等于当前区间右边界的lowbit（拆分区间的递推关系），自然可以想到，将区间$(i - lowbit(i),i]$的和存储到 index = i的位置

  • 因此定义$tree$数组，对于任意$tree[i]$，其存储范围为 $(i-lowbit(i),i]$区间的和，如下：

任意前缀和 $C[i]$计算，按照上述拆分过程，可以转化为不断的减去最右边一的过程

1
2
3
for(int index = i;index > 0;index -= lowbit(index)):
	//index -= lowbit(index) 就是类似于14拆分过程中的找所有2次幂过程
	C[i] += tree[index]

如何支持单点修改

若修改 $f[i]$，需要修改所有包含$f[i]$ 的 $tree[index]$, 我们要找到所有包含当前元素的区间，假设 $tree[idx]$ 包含 $f[i]$，则 $i$一定满足:

来自博客Binary indexed tree-树状数组 的形象解释

代码实现

lowbit()函数

1
2
3
public int lowbit(int x){
	return x & -x;
}

求前缀和

1
2
3
4
5
6
7
8
9
//预先处理好的子区间和数组
int tree[maxIndex]
public int query(int index){
	int result = 0;
	for(;index > 0;index++){
		result += tree[index];
	}
	return result;
}

更新方法

1
2
3
4
5
6
7
//预先处理好的子区间和数组
int tree[maxIndex]
public int update(int index, int val){
    for (int pos = index; pos < maxIndex; pos += lowbit(pos))
        //以加法为例
        tree[pos] += x;
}

初始化树状数组

wekipedia上的一个从数组[1,2,3,4,5]构建树状数组的过程：

BITDemo.gif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int tree[maxIndex]
//待求和数组
int aim[maxIndex]
//1.调用update方法（复杂度O(nlogn)）
for(int i = 1;i < maxIndex;i++){
    update(i, aim[i]);
}

//2.前缀和法(tree[i] = preSum[i] - preSum[i - lowbit(i)])
// 	复杂度O(n)
int preSum[maxIndex];
for(int i = 1;i < maxIndex;i++){
    preSum[i] = preSum[i - 1] + aim[i];
    tree[i] = preSum[i] - preSum[i - lowbit(i)];
}

模板题目

  1. luogu P3374 :树状数组1
    • 使用scanner做输入会出现三个测试用例TLE（坑爹）
  2. luogu P3368 :树状数组2
    • 通过差分的思路，将树状数组支持的操作变为
      • 单点修改->区间修改
      • 区间查询->单点查询
  3. luogu P2880 ：牛飞盘比赛
    • 树状数组维护值从 区间和 变为 区间内最值
    • update操作变为最大值更新，查询操作递归完成

参考

  1. wikipidia：树状数组
  2. 博客：Binary indexed tree-树状数组
  3. 博客：算法学习笔记(2) : 树状数组
  4. 树状数组模板题