线段树模板

定义
线段树是一种特殊的二叉树，每个节点代表原数组的一段区间，根节点代表整个区间，叶节点代表长度为1的区间。
一般应用：
利用线段树快速求区间的最值，求和等。
使用延迟标记可以很好地支持区间修改。
单次修改和查询的时间复杂度都是O(log n)。
一：

题目描述

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

1.将某区间每一个数加上x

2.求出某区间每一个数的和
输入输出格式
输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例
输入样例#1：复制

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出样例#1：复制

11
8
20

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^，保证在int64/long long数据范围内）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100005;
ll n,m,a[maxn];
int cnt,rt;
struct Node{      
    ll sum；  //sum代表此区间的值。
    int lazy;  //lazy表示延迟标记，修改区间值时需要用到
    int l,r;   //左右区间
    int ls,rs;  //左右儿子
}node[maxn*2];
inline void pushup(ll x){     //求值更新区间
    ll lson=node[x].ls,rson=node[x].rs;
    node[x].sum=node[lson].sum+node[rson].sum;  //求值
    node[x].l=node[lson].l;   //更新区间
    node[x].r=node[rson].r;
}
inline void pushdown(ll x){      //标记下放
    ll lson=node[x].ls,rson=node[x].rs;
    node[lson].sum+=node[x].lazy*(node[lson].r-node[lson].l+1);
    node[rson].sum+=node[x].lazy*(node[rson].r-node[rson].l+1);
    node[lson].lazy+=node[x].lazy;
    node[rson].lazy+=node[x].lazy;
    node[x].lazy=0;    //标记还原
}
inline void build(ll L,ll R,ll cur){     //建树
    if(L==R){    //如果是叶节点
        node[cur].ls=node[cur].rs=-1;    //没有儿子
        node[cur].l=node[cur].r=L;
        node[cur].sum=a[L];
        node[cur].lazy=0;
        return;
    }
    ll mid=(L+R)/2;
    node[cur].ls=++cnt,node[cur].rs=++cnt;
    build(L,mid,node[cur].ls);         //递归建树
    build(mid+1,R,node[cur].rs);
    pushup(cur);          //更新区间lazy
}
inline ll query(ll L,ll R,ll cur){         //求和函数
    if(L<=node[cur].l && node[cur].r<=R)
        return node[cur].sum;     //在所求区间内
    pushdown(cur);       //标记下放
    ll tot=0;
    ll mid=(node[cur].l+node[cur].r)/2;
    if(L<=mid)  tot+=query(L,R,node[cur].ls);   //区间落在左子树
    if(mid<R)   tot+=query(L,R,node[cur].rs);   //区间落在右子树
    return tot;
}
inline void update(ll L,ll R,ll c,ll cur){   //修改区间   
    if(L<=node[cur].l && node[cur].r<=R){   //落在区间内
        node[cur].sum+=c*(node[cur].r-node[cur].l+1);
        node[cur].lazy+=c;
        return; 
    }
    pushdown(cur);  //标记下放
    ll mid=(node[cur].l+node[cur].r)/2;
    if(L<=mid)  update(L,R,c,node[cur].ls);
    if(mid<R)   update(L,R,c,node[cur].rs);
    pushup(cur);   //修改子树
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(register int i=1;i<=n;i++)
        scanf("%lld",&a[i]);    
    rt=++cnt;    //根节点编号为1
    build(1,n,rt);     //建树
    for(register int i=1;i<=m;i++){
        ll x;
        scanf("%lld",&x);
        if(x==1){
            ll aa,bb,cc;
            scanf("%lld%lld%lld",&aa,&bb,&cc);
            update(aa,bb,cc,rt);
        } 
        else{
            ll aa,bb;
            scanf("%lld%lld",&aa,&bb);
            printf("%lld
",query(aa,bb,rt));
        }
    }
    return 0;
}

二:

题目描述

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

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和
输入输出格式
输入格式：

第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数乘上k

操作2：格式：2 x y k 含义：将区间[x,y]内每个数加上k

操作3：格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果

输出格式：

输出包含若干行整数，即为所有操作3的结果。