题目：已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x；2.求出某区间每一个数的和。
解法：如题，模版题。需要加上 lazy 标记，也就是我的 upd。lazy 标记的思路就是对一个结点更新（算和）了，但不继续更新它下面的结点，而是标记下来（每个数需加上的值）。注意——边界判断，不能调用a[-1]之类的。而对于叶子结点的upd，为0或有值都没有关系，反正它已经没有孩子了嘛。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6 #define N 100010
7 typedef long long LL;
8
9 int n,m,len=0;
10 struct node{int l,r,lc,rc;LL d,upd;}a[2*N];
11
12 void build(int l,int r)
13 {
14 int x=++len;
15 a[x].l=l,a[x].r=r,a[x].d=a[x].upd=0;
16 a[x].lc=a[x].rc=-1;
17 if (l<r)
18 {
19 int mid=(l+r)>>1;
20 a[x].lc=len+1,build(l,mid);
21 a[x].rc=len+1,build(mid+1,r);
22 }
23 }
24 void updata(int x)
25 {
26 if (!a[x].upd) return;
27 LL d=a[x].upd;
28 a[x].upd=0;
29 int lc=a[x].lc,rc=a[x].rc;
30 if (lc!=-1) a[lc].d+=d*(a[lc].r-a[lc].l+1),a[lc].upd+=d;
31 if (rc!=-1) a[rc].d+=d*(a[rc].r-a[rc].l+1),a[rc].upd+=d;//-1 +=
32 }
33 void ins(int x,int l,int r,int d)
34 {
35 if (a[x].l==l && a[x].r==r) {a[x].d+=d*(a[x].r-a[x].l+1);a[x].upd+=d;return;}
36 updata(x);//
37 int lc=a[x].lc,rc=a[x].rc,mid=(a[x].l+a[x].r)>>1;
38 if (r<=mid) ins(lc,l,r,d);
39 else if (l>mid) ins(rc,l,r,d);
40 else ins(lc,l,mid,d),ins(rc,mid+1,r,d);
41 a[x].d=a[lc].d+a[rc].d;
42 //a[x].upd=a[lc].upd+a[rc].upd;
43 }
44 LL query(int x,int l,int r)
45 {
46 updata(x);
47 if (a[x].l==l && a[x].r==r) return a[x].d;
48 int lc=a[x].lc,rc=a[x].rc,mid=(a[x].l+a[x].r)>>1;
49 if (r<=mid) return query(lc,l,r);
50 else if (l>mid) return query(rc,l,r);
51 else return query(lc,l,mid)+query(rc,mid+1,r);
52 }
53 int main()
54 {
55 scanf("%d%d",&n,&m);
56 int x,y,k; LL d;
57 build(1,n);
58 for (int i=1;i<=n;i++)
59 {
60 scanf("%lld",&d);
61 ins(1,i,i,d);
62 }
63 while (m--)
64 {
65 scanf("%d",&k);
66 if (k==1)
67 {
68 scanf("%d%d%lld",&x,&y,&d);
69 ins(1,x,y,d);
70 }
71 else
72 {
73 scanf("%d%d",&x,&y);
74 printf("%lld\n",query(1,x,y));
75 //for (int i=1;i<=len;i++)
76 // printf("%d %d %d %lld %lld\n",i,a[i].l,a[i].r,a[i].d,a[i].upd);
77 }
78 }
79 return 0;
80 }