线段树

#include<iostream>       //——————————>debug 了一上午才把这个程序运行的过程在脑子里有了思路 
#include<string.h>       //头文件就不多说了 
#include<stdlib.h>
#define maxsize 10000  //这个可定义其他数----------->这个 主要是控制数组的大小， 
using namespace std;
struct node {                      //结构体 ，相当于创建的二叉树 
    int left, right;               //记录的左右子节点 
    int lazy, sum;                 //lazy记录延迟，sum记录在这个节点的左右端点之间的总和 
    int mid() { return (left + right) / 2; }
}T[maxsize<<2];//相当于扩大了4倍----------------------->这个时学过数据结构的都知道度为0的比度为2的多1有n个数说明n个叶子节点要建立2*n-1个点但是 
               //因为假若数据相对较大，则访问到了最后一行，则可能用到   n<<1  这种情况就会越界会re所以开4倍 
void pushup(int rt)        //向上更新sum的值 
{
    T[rt].sum = T[rt << 1].sum + T[rt << 1 | 1].sum;
}
void pushdown(int rt, int m)  //向下更新lazy和sum的值，主意好区间，因为整篇都是做区间的多于右区间 
{   
    if (T[rt].lazy)
    {
        T[rt << 1].lazy += T[rt].lazy;
        T[rt << 1 | 1].lazy += T[rt].lazy;   //更新lazy值 
        T[rt<<1].sum += T[rt].lazy*(m - (m >> 1));//这说明如果是n为奇数 则左半部分就是多1
        T[rt<<1|1].sum += T[rt].lazy *(m >> 1);//注意>>的优先级
        T[rt].lazy = 0; //不能忘了把这个标志置为0
    }
}
void create(int rt, int l, int r)
{
    T[rt].left = l;                             //创建时对左节点和右节点进行赋值 
    T[rt].right = r;
    T[rt].lazy = 0; 
    if (T[rt].left == T[rt].right)              //不能写下边了，且只有当到也叶子节点时也就是当节点的左边等于右边时才赋值 
    {                                           //不然地址就错了 ，因为递归调用返回时输入值的地址i就是错的 
        cin >> T[rt].sum;                       //或是赋值为0，
        return;
    }
    create(rt << 1, l, T[rt].mid());  //这个创建进过摸你可以看出如果n为奇数返回的中间值时中间的奇数，则说明创建的时候左边可能比右边的多 
    create(rt << 1 | 1, T[rt].mid()+1, r);  //不能忘记mid（）+1   
    pushup(rt);    //创建完之后别忘了向上传递更新上边的sum值 
}
void Union(int rt, int l, int r, int c)//rt 为根节点，在l和r的范围内部的数都加上c
{
    if (T[rt].left == l&&T[rt].right == r)          //这里就用到lazy做延迟了，这个节点lazy记录的是这个区间内要加的但是不向下进行了， 
    {                                             //就省了时间，sum记录的是这个姐弟啊你左右端点内的所有要加的值的和 
        T[rt].lazy += c;                            
        T[rt].sum += c*(T[rt].right - T[rt].left + 1);  // 
        return;
    }
    if (T[rt].left == T[rt].right) return;
    pushdown(rt, T[rt].right - T[rt].left + 1);
    if (r <= T[rt].mid())           //因为如果为奇数，则返回的中间值时中间的奇数， 
        Union(rt << 1, l, r, c);
    else if (l > T[rt].mid())
        Union(rt << 1 | 1, l, r, c);
    else {
        Union(rt << 1, l, T[rt].mid(), c);
        Union(rt << 1 | 1, T[rt].mid()+1, r, c);
    }
    pushup(rt);    //这个是向上更新，其实就是用下边的两个点来更新这个点
}
int sum(int rt, int l, int r)//求出在某个范围l到r内的和
{
    int ans=0;
    if (T[rt].left == l&&T[rt].right==r)  //看好代码别写错了 
        return T[rt].sum;
    pushdown(rt, T[rt].right - T[rt].left + 1);
    if (r <= T[rt].mid())         /////////////////////这个必须是小于等于因为 若是奇数则返回的时中间的奇数则就是返回的数比另一半多1，所以就小于等于 
        ans+=sum(rt << 1, l, r);
    else if (l >T[rt].mid())
        ans+=sum(rt << 1 | 1, l, r);
    else {
        ans+=sum(rt << 1, l, T[rt].mid());
        ans+=sum(rt << 1 | 1, T[rt].mid()+1, r);//不要忘记是mid()+1;
    }
    return ans;
}
int main()
{
    int n, m, a, b, c;
    while (cin >> n >> m)
    {
        create(1,1,n);
        while (m--)
        {
            char s;
            cin >> s;
            if (s == 'Q')     //查询在a，b区间的总和 
            {
                cin >> a >> b;
                cout << sum(1, a, b)<<endl;
            }
            else if(s=='B'){      //在  a，b区间内每个节点都加上c 
                cin >> a >> b >> c;
                Union(1, a, b, c);
            }
        }
    }
}