1 #define Mid (l+r)/2

 　　2 #define Left root*2              //众所周知，一个节点的左儿子下标就是当前节点的下标(root)*2

 　　3 #define Right root*2+1           //一个节点的右儿子下标就是当前节点的下标(root)*2+1

 　　4 const long long maxn=1000000;

 　　5 struct tr{                       //用结构体代替一个节点

 　　6     long long left_son,right_son;//节点表示的区间left_son~right_son

 　　7     long long sum,lazy;          //该节点区间的和，以及臭名昭著的懒标记

 　　8 }tree[maxn*2+1];

 　　9 long long a[maxn*2+1];           //那个数组

　　10 long long n,m;                   //n表示a数组的数字个数，m表示操作次数

 　　1 void Build(long long root,long long l,long long r){//root表示当前遍历到的节点的下标,l和r表示表示l~r的区间

 　　2     tree[root].left_son=l;                         //赋值当前节点表示的区间

　　 3     tree[root].right_son=r;

　　 4     if(l==r){                                      //如果左指针与右指针重合说明遍历到了叶子节点，也就是最下方的节点

　　 5         tree[root].sum=a[l];                       //于是就给他赋上a数组的值其实a[l]也可以写a[r],无所谓

 　　6         return;                                    //接着返回构造下一个节点

　　 7     }

　　 8     Build(Left,l,Mid);                             //遍历他的左儿子(下标为Left)与右儿子(下标为Right),并且缩小区间用类似二分的方法

　　 9     Build(Right,Mid+1,r);

　　10     tree[root].sum=tree[Left].sum+tree[Right].sum; //当左右儿子都有值的时候就构造自己，然后返回构造自己的父亲

　　11 }

　　1 void Lazy(long long root){                                                                //root表示当前节点

　　2     if(tree[root].lazy){                                                                  //如果当前节点有懒标记

　　3         tree[Left].sum+=tree[root].lazy*(tree[Left].right_son-tree[Left].left_son+1);     //那么就会修改当前节点的值首先要改左儿子与右儿子的值

　　4         tree[Right].sum+=tree[root].lazy*(tree[Right].right_son-tree[Right].left_son+1);  //既然是区间修改，那么本题要求区间加某个数，所以当前儿子要加上他所表示的区间的数的个数个要加上的那个数

　　5         tree[Left].lazy+=tree[root].lazy;                                                 //改了左右儿子的值就要改左右儿子的左右儿子的值，所以也要往下修改所以就要使用当前节点儿子的懒标记来修改孙子

　　6         tree[Right].lazy+=tree[root].lazy;

　　7         tree[root].lazy=0;                                                                //当前节点修改成功（还要改儿子）

　　8     }

　　9 }

　　 1 void Update(long long root,long long l,long long r,long long num){         //root的表示当前节点,l和r表示要修改的区间，num表示要加的数
　　 2     if(r<tree[root].left_son||tree[root].right_son<l)return; 　　　　　　　　//如果当前找到的区间不是理想区间那么就返回
　　 3     if(l<=tree[root].left_son&&r>=tree[root].right_son){　　　　　　　　　　　//如果是当前的区间

　　 4         tree[root].sum+=num*(tree[root].right_son-tree[root].left_son+1);　//那么就修改当前的值，与之前懒标记中的方法类似

　　 5         tree[root].lazy+=num;　　　　　　　　　　　　　　　　　　　　　　　　　  //由于还要修改儿子，所以标记懒标记，然后退出继续寻找合适区间

　　 6         return;

　　 7     }

　　 8     Lazy(root);                                    //修改儿子节点
　　 9     Update(Left,l,r,num);　　　　　　　　　　　　　　　//遍历左右儿子

　　10     Update(Right,l,r,num);

　　11     tree[root].sum=tree[Left].sum+tree[Right].sum; //当前节点的值赋值成左右儿子相加的和
　　12 }

　　1 long long Search(long long root,long long l,long long r){　　　　　　　　　　　　//root代表当前节点,l和r表示要查找的区间

　　2     if(r<tree[root].left_son||tree[root].right_son<l)return 0;　　　　　　　　　//如果不是想找的区间就返回没有值0

　　3     if(l<=tree[root].left_son&&r>=tree[root].right_son)return tree[root].sum;//如果是满意的区间那么就返回这个区间的值

　　4     Lazy(root);　　　　　　　　　　//将未修改的有懒标记的值加以修改

　　5     long long ans=0;　　　　　　　//开一个数记录和

　　6     ans+=Search(Left,l,r);      //加上左儿子的值

　　7     ans+=Search(Right,l,r);　　　//加上右儿子的值

　　8     return ans;　　　　　　　　　　//返回答案

　　9 }//大功告成~~QWQ