洛谷 P3374 【模板】树状数组 1 线段树版

传送门

　　题目描述：

　　已知一个数列，你需要进行下面两种操作：

　　1.将某一个数加上x

　　2.求出某区间每一个数的和

　　这道题看名字就知道是树状数组的模板题，但是菜鸡的我想熟悉线段树，所以用了线段树。

　　思路没有什么好说的(如果不知道怎么做的，建议先学习树状数组)，详情看代码。

　　一些小细节：

　　　　1.运算都用位运算加速

　　　　2.不要用cin,cout，亲测超时

　　　　3.对于根node，

　　　　　　左儿子是 node * 2 ---->> node << 1;

　　　　　　右儿子是 node * 2 + 1 ---->> node<<1 | 1;

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int N = 5e5 + 10;
 5 
 6 int n, m;
 7 int tree[N*4];
 8 
 9 
10 //不用建树，因为你会发现代码是一样的。。。亲测 
11 
12 //在pos上加上X 
13 void update(int node, int l, int r, int pos, int x)
14 {
15     if(l == r)    {tree[node] += x; return;}
16     int mid = (l + r) >> 1;
17     if(mid >= pos)    update(node<<1, l, mid, pos, x);
18     else            update((node<<1)|1, mid+1, r, pos, x);
19     tree[node] = tree[node<<1] + tree[(node<<1)+1]; 
20 }
21 
22 //查询区间[L, R]的和 
23 int query(int node, int l, int r, int L, int R)
24 {
25     if(L > r || R < l)        return 0;
26     if(L <= l && R >= r)    return tree[node];
27     int mid = (l + r) >> 1;
28     return query(node<<1, l, mid, L, R) + query((node<<1)|1, mid+1, r, L, R);
29 }
30 
31 int main()
32 {
33     scanf("%d %d", &n, &m);
34     for(int i = 1; i <= n; i++)    
35     {
36         int x;
37         scanf("%d", &x);
38         update(1, 1, N, i, x);
39     }
40     for(int i = 0; i < m; i++)
41     {
42         int op, x, y;
43         scanf("%d %d %d", &op, &x, &y);
44         if(op == 1)    update(1, 1, N, x, y);
45         else        printf("%d\n", query(1, 1, N, x, y));
46     }
47     return 0;
48 }