疯狂的区间 树状数组

缘起

【1】中我们使用树状数组给出了一个点相关的区间个数的求法. 本文将使用树状数组给出区间相关的点的操作.

问题:

给定一个整数序列a, 对a有以下操作

① 修改操作：将A[L..R]之间的全部元素值加上C,记为(L,R,C)；② 询问：求此时A[x]的值。

分析

a[i]最终的值=a[i]初始值+累计的改变的值.

注意累计两个字. 这就是使用树状数组的契机. 而注意, 

1
给a[i,...,j]+val等价于给a[i,...,n]+val和 给 a[j+1,...,n]-val

所以我们只需关注给a[i,…,n]+val 这种操作即可. 令数组b[i]的定义为

伊始是0数组, 即

1
b[1]=b[2]=...=b[n]=0 ， 其中b的0索引不用于存储数据

一旦进行 a[i,..,n]+val的操作的话, b[i]+=val.

令c是b的树状数组. 则此时需要维护了

则a[i]最后的累加量就是部分和b[1,..,i] (可以通过c在logn时间内完成求和), 这是因为 b[i+1,…n]是对a[i+1,..,n]+val，这影响不到a[i]的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
#define LOCAL
using namespace std;
const int N = 7;
int c[1+N],a[1+N]={0,1,5,6,3,2,7,8};//0索引不用,c是分析中说的树状数组

int lowbit(int x){return x&(-x);}

void update(int s, int val) // 给[s,...,N]全部+val, 如分析所言, 其实就是维护树状数组c
{
	if (s>N) return;
	while(s<=N)
	{
		c[s]+=val;
		s+=lowbit(s);
	}
}

int partialsum(int i) // 获取部分和b[1,...,i], 使用树状数组c在logn时间内获取
{
	int sum = 0;
	while(i)
	{
		sum+=c[i];
		i-=lowbit(i);
	}
	return sum;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int s,e, val;
	char cmd;
	puts("输入你想进行的操作, U表示更新, Q表示查询, X表示退出");
	while((cmd = getchar())!='X')
	{
		if (cmd == 'U')
		{
			puts("输入你想操作的区间和改变的值, 格式为 s e val");
			scanf("%d%d%d", &s, &e, &val);
			update(s,val);
			update(e+1, -val); // 反向操作
		}
		else if (cmd == 'Q')
		{
			puts("输入你想查询的元素");
			scanf("%d", &s);
			printf("%d\n", a[s]+partialsum(s));
		}
		puts("输入你想进行的操作, U表示更新, Q表示查询, X表示退出");
		getchar(); // 吸收printf带来的多余换行符
	}
	return 0;
}
/*
测试数据
U
1 4 2
U
2 3 7
Q
2
Q
4
Q
7
U
2 7 1
Q
4
X
*/

参考

【1】https://yfsyfs.github.io/2019/06/05/poj-2481-Cows-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/