UESTC 1057

题目链接：http://acm.uestc.edu.cn/#/problem/show/1057

线段树的第一题，看着题解和讲解，自己把模板一点点慢慢码出来的。

线段树讲解：http://www.cnblogs.com/TenosDoIt/p/3453089.html

2018-5-1更新

今天又看了一下线段树模板，对于update函数进行补充一点自己的看法吧：

1、

update函数其实秉承着一种思路：

我现在要对某个区间[l,r]进行更新的某个值x，从当前树根root往下dfs有三种情况：

　　①root所统领的区间和[l,r]并不相交，也就是说我们没有任何关系，显然什么都不做直接return；

　　②root所统领的区间被[l,r]包含，那么我直接把root这个节点的值val（可能是区间sum，也可能是区间max/min）更新一下，并且打个lazy标记，表示：我很懒，我到这里就不想往下走了，我给自己打个标记，以后要是要用到我的左右儿子，你记得把我这个lazy标记传给儿子们更新（pushdown）。

　　③root所统领的区间包含[l,r]，诶好像要用到我的儿子们了，那我记起来我得看看之前有没有lazy标记，若是有不能忘了先传给儿子更新（pushdown）（虽然懒，但不能出错）；然后去更新树根为root*2和root*2+1的两个子树。

　　（pushdown函数呢，它是这样的：

　　　pushdown(root)，代表我这个root为根的树要把我的标记传给儿子们了，怎么传呢：

　　　　　①首先，既然我有这个标记，说明我统领的这个区间，下面所有的子区间，不管是谁，都得跟着lazy更新；

　　　　　　所以左右儿子不用想了，你俩直接把你们的节点的值val（sum/max/min…）更新，肯定不会错的。

　　　　　②然后，子随父懒，儿子们更新完自己的val，也不想往下走了，算了，一样打个lazy标记吧。

　　　　　③最后，老爹的lazy传给儿子了，了却了一桩心事，lazy标记给他置零吧。

　　　）

　　最终再回到③，root老爹一看，我之前欠下的债lazy已经父债子还了，我现在要更新的x值也已经传给俩儿子了……不能忘了，要根据俩儿子的val更新一下自己的val。

同样的，query关于pushdown和pushup的操作也是类似于上面的update的。

有一些注意点，比如要开4倍的MAXN，否则在数据较大时会RE，引用来自CSDN上的一段话：

 1 #include<cstdio>
 2 #define MAXN 100000+5
 3 typedef long long ll;
 4 struct Node{
 5     int l,r;
 6     ll sum,lazy;
 7     void update(ll x)
 8     {
 9         sum+=(r-l+1)*x;
10         lazy+=x;
11     }
12 }node[4*MAXN];
13 int n,m,a[MAXN];
14 void pushdown(int root) //若存在lazy标记，根据lazy更新左右子节点，并将自己的lazy标记置零
15 {
16     if(node[root].lazy)
17     {
18         node[root*2].update(node[root].lazy);
19         node[root*2+1].update(node[root].lazy);
20         node[root].lazy=0;
21     }
22 }
23 void pushup(int root)
24 {
25     node[root].sum=node[root*2].sum+node[root*2+1].sum;
26 }
27 void build(int root,int l,int r)
28 {
29     node[root].l=l; node[root].r=r;
30     node[root].sum=0; node[root].lazy=0;
31     if(l==r) node[root].sum=a[l];
32     else
33     {
34         int mid=l+(r-l)/2;
35         build(root*2,l,mid);
36         build(root*2+1,mid+1,r);
37         pushup(root);
38     }
39 }
40 void update(int root,int st,int ed,int val)
41 {
42     if(st>node[root].r || ed<node[root].l) return;
43     if(st<=node[root].l && node[root].r<=ed) node[root].update(val);
44     else
45     {
46         pushdown(root); //若当前节点有lazy标记，需要先push下去才能进行左右子节点更新
47         update(root*2,st,ed,val);
48         update(root*2+1,st,ed,val);
49         pushup(root);
50     }
51 }
52 ll query(int root,int st,int ed)
53 {
54     if(ed<node[root].l || node[root].r<st) return 0;
55     if(st<=node[root].l && node[root].r<=ed) return node[root].sum;
56     else
57     {
58         ll ans=0;
59         pushdown(root);
60         ans+=query(root*2,st,ed);
61         ans+=query(root*2+1,st,ed);
62         pushup(root);
63         return ans;
64     }
65 }
66 int main()
67 {
68     scanf("%d",&n);
69     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
70     build(1,1,n);
71     scanf("%d",&m);
72     for(int i=1;i<=m;i++)
73     {
74         int l,r,v;
75         scanf("%d%d%d",&l,&r,&v);
76         update(1,l,r,v);
77         printf("%lld
",query(1,l,r));
78     } 
79 }