暑期竞赛培训 Day 11—— < 树状数组 >
树状数组
一、适用范围：
树状数组是一个查询和修改复杂度都为 log(n)的数据结构，常常用于查询任意区间的所有元素之和。与前缀和的区别是支持动态修改, log(n)的时间进行修改，log(n)查询。
支持如下操作：
- [1] 单点修改区间查询
- [2] 区间修改单点查询
- [3] 区间修改区间查询
二、算法原理
1.树状数组较好的利用了二进制。它的每个节点的值代表的是自己和前面一些连续元素的和。至于到底是前面哪些元素，这就由这个节点的下标决定。
2.设节点的编号为 i，那么：
所以：
C[1] = A[1] // lowbit(1)个元素之和
C[2] = C[1] + A[2] = A[1] + A[2] // lowbit(2)个元素之和
C[3] = A[3] // lowbit(3)个元素之和
C[4] = C[2] + C[3] +A[4] = A[1] + A[2] + A[3] +
A[4] // lowbit(4)个元素之和
C[5] = A[5]
C[6] = C[5] + A[6] = A[5] + A[6]
C[7] = A[7]
C[8] = C[4] + C[6] + C[7] + A[8] = A[1] + A[2] +A[3] + A[4] + A[5] + A[6] + A[7] + A[8]
显然前缀和可以通过区间和求解出来：
sum[1] = c[1]
sum[2] = c[2]
sum[3] = c[3] + c[2]
sum[4] = c[4]
sum[5] = c[5] + c[4]
sum[6] = c[6] + c[4]
sum[7] = c[7] + c[6] + c[4]
sum[8] = c[8]
例如求解sum[7] 见下图：
我们发现：
7 - lowbit(7) = 6
6 - lowbit(6) = 4
4 - lowbit(4) = 0
sum[7] = c[7] + c[6] + c[4]
所以当我们维护出 c 数组，则我们可以通过循环不停的减
lowbit 直到为 0 计算出前缀和。
前缀和代码实现
int get_sum(int i){
int res=0;
for(;i;i-=lowbit(i))
res+=c[i];
return res;
}
点更新
当我们需要对原始序列的某个元素 a[i] 更新成 a[i]+x 时，我们只
需把树状数组中包含了 a[i] 的区间数组 c[i] 进行即可。
如图，如果 a[3] 进行了更新，包含了 a[3] 的区间只有
c[3]，c[4],c[8] 我们只需更新这三个区间即可。如何遍历这三个区间呢？我们发现：
3 + lowibt(3) = 4
4 + lowbit(4) = 8
我们可以通过循环不停的加 lowbit 直到大于 n ，对相应的
区间进行更新即可。
向上更新代码实现:
void Update(int i,int x){
for(;i<=n;i+=lowbit(i))
c[i]+=x;
}
——————————————华丽的分割线QWQ
三、 实际应用：
了解了这么多
那么我们就来看道简单题吧(我目前唯一能看懂的一道题QWQ)
题目描述：
单点修改区间求和
如题，已知一个数列，你需要进行下面两种操作：
将某一个数加上 x
求出某区间每一个数的和
输入格式
第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项初始值。
接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：
1 x k 含义：将第 x 个数加上 k
2 x y 含义：输出区间 [x,y] 内每个数的和
输出格式
输出包含若干行整数，即为所有操作 2 的结果
样例输入
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
样例输出
14
16
解题步骤：
根据刚才前缀和与向上更新的基础，现在只需要用一个一个求 sum[x] 与 sum[y] 的值就行了,另外，题目意思是求 x —— y 的区间和，那么 sum[x]就要变成 sum[x-1] ,这样就完成啦！！！(再码就寄了QWQ)
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m;
int c[maxn];
int lowbit(int x){
return x&(-x);
}
void Update(int i,int x){
for(;i<=n;i+=lowbit(i))
c[i]+=x;
}
int get_sum(int i){
int res=0;
for(;i;i=i-lowbit(i))
res+=c[i];
return res;
}
void sol(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
Update(i,x);
}
while(m--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1) Update(x,y);
else printf("%d\n",get_sum(y)-get_sum(x-1));
}
}
int main(){
sol();
return 0;
}