学习笔记-树状数组(三)
树状数组(一)
树状数组(二)
通过树状数组的基本操作,我们可以实现区间查询和单点修改。结合差分,又可以实现单点查询和区间修改。那么,怎么才能像线段树一样,快速实现区间查询,区间修改呢?
由差分到前缀和
既然要区间修改,那么一定要使用差分数组而不是原始数组
由上一篇可见,c1+c2+...+ci=ai
也就是说,差分数组的前缀和=原数值
而原数值的前缀和=前缀和
所以前缀和=差分数组的前缀和的前缀和
虽然听起来有点绕,但是结论是这样
简单尝试推导
那么,可以推出如下算式
a1+a2+a3+...+ai
=(c1)+(c1+c2)+(c1+c2+c3)+...+(c1+c2+...+ci)
=c1*(i)+c2*(i-1)+c3*(i-2)+...+ci-1*2+ci*1
可以看出来,差分数组的第j个数会被加i-j+1次
...然而貌似还是很不方便
进一步推导
运用一些简单的数学知识(这块我也讲不明白),最后推导完毕的式子是这样:
a1+a2+...+ai
=(i+1)*(c1+c2+...+ci)-(c1*1+c2*2+...+ci*i) ——如果你不想写线段树,请牢记这个推导式
经过各种玄学等式变形,我们得到了这样一个算式,可以保证差分数组的第i个数被加i遍。
这样,只要建立两个差分数组的树状数组,一个存储ci、一个存储ci*i,就可以区间修改查询了。
结论(画重点)
为了方便调用,我们把树状数组建成二维tree[0][i]表示ci,tree[1][i]表示ci*i
那么在使用单点修改函数对差分数组单点修改时,要在tree0,i加k,在tree1,i加i*k
想要查询前缀和时,就可以计算(i+1)*(tree0,i的前缀和)-(tree1,i的前缀和)
程序实现
区间修改
我们在基础程序上加一维f,作为区分ci和ci*i两数组的变量
1 void add(int x,int k,bool f)
2 {
3 while(x<=n)
4 {
5 tree[f][x]+=k;
6 x+=lowbit(x);
7 }
8 }
然后把它套在前面加粗的那个斜体结论上
1 void update(int x, int k)
2 {
3 add(x, k, 0);
4 add(x, x*k, 1);
5 }
这就是完整的对差分数组单点修改函数
那么,使用差分数组的O(1)修改的特点,在主程序里进行两次update操作,就可以完成区间修改
比如要对x到y加上k,就可以这样
update(x, k);
update(y+1, -k);
区间查询
和区间修改的变化一样的步骤,首先添加维度
1 int sch(int x, bool f){
2 int ans = 0;
3 while(x >= 1){
4 ans += tree[f][x];
5 x -= lowbit(x);
6 }
7 return ans;
8 }
然后套用结论
1 int sum(int x)
2 {
3 int ans = (x + 1) * (sch(x, 0)) - sch(x, 1);
4 return ans;
5 }
最后,利用前缀和数组的O(1)查询的特点,在主程序里面调用两次sum,就可以了
比如要求出x到y的区间和,赋值给res,就可以这样
res = sum(y) - sum(x - 1);
例题
LGOJ-P3372
题目大意
实现区间修改和查询
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
程序实现
1 #include<cstdio>
2 #include<cctype>
3 #define ll long long
4 using namespace std;
5 ll n, m, tree[2][100010];
6 inline ll read(){
7 char ch = getchar();
8 ll f = 1, x = 0;
9 while(!isdigit(ch)){
10 if(ch == '-') f = -1;
11 ch = getchar();
12 }
13 while(isdigit(ch)){
14 x *= 10;
15 x += (ch & 15);
16 ch = getchar();
17 }
18 return f * x;
19 }
20 ll lowbit(ll x){
21 return x & (-x);
22 }
23 void add(ll x,ll k,ll f)
24 {
25 while(x<=n)
26 {
27 tree[f][x]+=k;
28 x+=lowbit(x);
29 }
30 }
31 void update(ll x, ll k)
32 {
33 add(x, k, 0);
34 add(x, x*k, 1);
35 }
36 ll sch(ll x, ll f){
37 ll ans = 0;
38 while(x >= 1){
39 ans += tree[f][x];
40 x -= lowbit(x);
41 }
42 return ans;
43 }
44 ll sum(int x)
45 {
46 ll ans = (x + 1) * (sch(x, 0)) - sch(x, 1);
47 return ans;
48 }
49 int main(){
50 n = read(), m = read();
51 for(ll i = 1, a = 0, b = 0; i <= n; i++){
52 b = read();
53 update(i, b - a);
54 a = b;
55 }
56 while(m--){
57 if(read() == 1){
58 ll x, y, z;
59 x = read(); y = read(); z = read();
60 update(x, z); update(y + 1, -z);
61 }
62 else{
63 ll x, y;
64 x = read(); y = read();
65 printf("%lld\n", (sum(y) - sum(x - 1)));
66 }
67 }
68 return 0;
69 }
转载于:https://www.cnblogs.com/Juruo1103/p/9972778.html