洛谷 P3368 【模板】树状数组 2(区间修改点查询) 题目描述 输入输出格式 输入输出样例 说明 解题思路: AC代码:
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的值
输入输出格式
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x 含义：输出第x个数的值
输出格式：
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
解题思路:
因为树状数组只支持单点修改,所以我们引入了一个神奇的东西——差分数组(差分数组储存的是当前元素减前一个元素的差),每当我们要修改区间[x,y]的值时,只需将差分数组t[x]和t[y+1]加上我们要修改的值即可.(原理画图即可理解).
AC代码:
1 #include<cstdio>
2 #define lowbit(x) x & -x
3
4 using namespace std;
5
6 int n,m;
7 long long t[500005];
8
9 void add(int x,long long num) {
10 while(x <= n) {
11 t[x] += num;
12 x += lowbit(x);
13 }
14 }
15
16 long long qq(int x) {
17 long long ans = 0;
18 while(x) {
19 ans += t[x];
20 x -= lowbit(x);
21 }
22 return ans;
23 }
24
25 int main()
26 {
27 scanf("%d%d",&n,&m);
28 long long last = 0, now;
29 for(int i = 1;i <= n; i++) {
30 scanf("%lld",&now);
31 add(i,now - last);
32 last = now;
33 }
34 int _flag;
35 while(m--) {
36 scanf("%d",&_flag);
37 if(_flag == 1) {
38 int x,y;
39 long long k;
40 scanf("%d%d%lld",&x,&y,&k);
41 add(x,k);
42 add(y + 1, -k);
43 }
44 if(_flag == 2) {
45 int x;
46 scanf("%d",&x);
47 printf("%lld
", qq(x));
48 }
49 }
50 return 0;
51 }