树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改、区间求和。
lowbit数组
lowbit[x] 等于 x 这个数的二进制表示下最低位 1 所对应的十进制数值。（x 默认为非负）
例如：lowbit[44] = lowbit[(101100)2] = (100)2 = 4
- 计算
那么怎么计算呢，当我们对lowbit[x]进行二进制计算时，可以发现 x & (~x + 1) （~：取反）的计算结果即为lowbit[x]。
又已知计算机采用的是补码，非负数的补码是其原码本身，负数补码为除最高位外每位取反再加 1。那么 （~x + 1）= -n成立，则lowbit[x] = x & (~x + 1) = n & (-n)
树状数组思想
单点修改，区间查询
如下图，横坐标是 x，纵坐标是对应的 lowbit[x]。其形状像一棵二叉树，当我们连接起来父子节点（绿线）时，可以发现，求左孩子的父节点对应的 x 时，可以利用公式 x + lowbit[x]，如 x=5 的父节点是 x+lowbit[5]=6 即 x=6 是其父节点。同理右孩子的父节点是 x - lowbit[x]。
接下来引入一个辅助数组c[i]，c[x] 值为下标是 i=x-lowbit[x]+1 递增到 x 的 a[i] 的和。（a 为原数组，为便于理解本文图中 x 轴的值为 a[x]，即 a[1] = 1、a[2] = 2等 ）
那么直观表示就是如下图所示蓝色区域覆盖的地方：
由此可发现当每次修改 x 对应位置的值时，需要同时修改被其他（蓝色）区域覆盖的 c 数组的值，通过观察可以发现，需要修改的那些区域就是 x 的所有直接/间接父节点，且 x 是那个父节点的左孩子，而求其父节点的公式上述已知：x + lowbit[x]。
所以单点更新的方法就是：从要更新的那个位置 i=x 开始循环，使 c[i] 数组更新其值，然后 i+=lowbit[i]，直到 i 更新到数组最大值即可。
同时我们可以发现，当查询前缀和时，每个位置对应的 c 数组值（蓝色区域）开始点所反映的直观表示是在它的上面 且 位于前面的某数（当前数减去其 lowbit 的值）的蓝色区域结束点，那么将它们首尾相连所得的 c 数组（蓝色区域）的和，即为当前位置的前缀和。而每个位置 x 的蓝色位置的值即为 x - lowbit[x]。
所有求区间和的方法是：从 i=x 开始，令一个初始化为0的变量sum逐个记录 c 数组（蓝色区域）的值，然后 i = i - lowbit[i] 循环，直到 i 到达0为之结束循环。最后sum的值就是 x 对应的前缀和，两前缀和相减即为对应的区间和。
区间修改，单点查询
定义一个查分数组 d，即d[i]=a[i]-a[i-1]。那么看如下图所示：
当区间2--4加 1后，差分数组只改变了第2个位置和第5个位置（蓝色字体值没变），观察又可发现2位置加了1，而5位置减了1（根据差分数组的计算性质可以解释）。那么可以利用这点来达到区间修改的等价，且服务于后面的单点查询。请接着往下看
下面我们计算差分数组的前缀和：d[i]=(a[i]-a[i-1]) + (a[i-1]-a[i-2]) + ... + (a[3]-a[2]) + (a[2]-a[1]) + a[1] = a[i]，则计算差分数组的前缀合就等于原给定序列的单点查询。因此用差分数组解决了区间修改和单点查询问题。
区间修改，区间查询
由于差分数组的前缀和是原数组的值，那么差分数组前缀和的前缀和是原数组的前缀和
每次计算差分数组前缀和的前缀和，那么每个差分数组的值被加的次数是有规律的，即d[1]被加次数最多，一共被加了x次（假设一共有x个数据），那么接下来的d[2]被加了x-1次，以此类推，那么原数组的前缀和为差分数组所有项被加的总和，即 d[i]×(x-i+1) （i从1到x）。然后做以下变化：
s1[i] 维护 d[i] 的前缀和；
s2[i] 维护 d[i]×i 的前缀和。
......
其他方法：采用线段树可以处理复杂的区间操作。
代码示例
单点修改，区间查询
import java.util.Scanner;
/**
* 单点修改，区间查询
*/
public class TreeArray1 {
static int n, m;
static int[] sum = null;
static int lowbit(int x){
return x & (-x);
}
static void add(int x, int c) {
while (x <= n){
sum[x] += c;
x += lowbit(x);
}
}
static int query(int x){
int ans = 0;
while (x > 0){
ans += sum[x];
x -= lowbit(x);
}
return ans;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
sum = new int[n+5];
for (int i=1; i<=n; i++){
int t = cin.nextInt();
add(i, t);
}
for (int i=0; i<m; i++){
int opt = cin.nextInt();
int x = cin.nextInt();
int y = cin.nextInt();
if (opt == 1){ //单点修改
add(x, y);
}else if (opt == 2){ //区间查询
int ans = query(y) - query(x-1);
System.out.println(ans);
}
}
}
}
区间修改，单点查询
import java.util.Scanner;
/**
* 区间修改，单点查询
*/
public class TreeArray2 {
static int n, m;
static int[] sum = null;
static int lowbit(int x){
return x & (-x);
}
static void add(int x, int c) {
while (x <= n){
sum[x] += c;
x += lowbit(x);
}
}
static int query(int x){
int ans = 0;
while (x > 0){
ans += sum[x];
x -= lowbit(x);
}
return ans;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
sum = new int[n+5];
int[] a = new int[n+5];
for (int i=1; i<=n; i++) a[i] = cin.nextInt();
int[] d = new int[n+5];
for (int i=1; i<=n; i++){
d[i] = a[i] - a[i-1];
add(i, d[i]);
}
for (int i=0; i<m; i++){
int opt = cin.nextInt();
if (opt == 1){ //区间修改
int l = cin.nextInt();
int r = cin.nextInt();
int c = cin.nextInt();
add(l, c);
add(r+1, -c);
}else if (opt == 2){ //单点查询
int x = cin.nextInt();
System.out.println(query(x));
}
}
}
}
网友评论