洛谷 P3372 线段树【模板1】

模板一是区间加修改和区间和

例题

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
struct Tree
{
    int l,r;//区间左右端点 
    long long int lazy;//延迟标记 
    int ls,rs;//左右子区间 
    long long int sum;//区间和 
};
int rt=1,cnt=2;
int n,i,m;
const int maxa=100000;
Tree tree[maxa<<1];//结构体模拟线段树 
long long int a[maxa+50];//初始数组 
void pushup(int x)//更新变动节点x 
{
    int lson=tree[x].ls;//左子节点 
    int rson=tree[x].rs;//右子节点 
    tree[x].sum=tree[lson].sum+tree[rson].sum;//当前节点的值为左右子节点的和 
    tree[x].l=tree[lson].l;//更新区间左端点 
    tree[x].r=tree[rson].r;//更新区间右端点 
}
void update(int p,int c,int cur)//单位置（节点）修改 
{
    if (tree[cur].l==tree[cur].r)//如果已是叶节点 
    {
        tree[cur].sum+=c;//修改 
        return ;
    } 
    //否则 
    long long int mid=(tree[cur].l+tree[cur].r)>>1;//区间中点 
    if (p<=mid) update(p,c,tree[cur].ls);//如果点p在该区间中间节点左边，递归当前节点的左儿子 
    else update(p,c,tree[cur].rs);//如果在右边，递归右儿子 
    pushup(cur);//更新 
}
void build(int L,int R,int cur)//构建线段树 
{
    if (L==R)//如果该节点区间长度为一，则是一个叶节点，存储 
    {
    	//cout<<L<<endl;
        tree[cur].ls=tree[cur].rs=-1;//无左右子节点 
        tree[cur].l=tree[cur].r=L;//左右端点为L或R 
        tree[cur].sum=a[L];//区间的值为初始数组中第L个值 
        tree[cur].lazy=0;
        return ;
    }
    long long int mid=(L+R)>>1;//否则开始二分查找 
    tree[cur].ls=cnt++;//节点数++ 
    tree[cur].rs=cnt++;//again 
    build(L,mid,tree[cur].ls);//构建该节点的左子树 
    build(mid+1,R,tree[cur].rs);//构建右子树 
    pushup(cur);//更新节点cur 
}
void pushdown(int x)//区间修改，整体加一个常数 
{
    int lson=tree[x].ls;//左子区间 
    int rson=tree[x].rs;//右子区间 
    tree[lson].sum+=tree[x].lazy*(tree[lson].r-tree[lson].l+1);//左子区间加上延迟标记*区间长度，整体加c 
    tree[rson].sum+=tree[x].lazy*(tree[rson].r-tree[rson].l+1); //同 
    tree[lson].lazy+=tree[x].lazy;
    tree[rson].lazy+=tree[x].lazy;//延迟标记下移 
    tree[x].lazy=0;//延迟标记释放 
}
void up_date(long long int L,int R,long long int c,int cur)//区间修改，增加一个常数c 
{//分割区间 
    if (L<=tree[cur].l&&tree[cur].r<=R)//是修改区间的子集 
    {
        tree[cur].sum+=c*(tree[cur].r-tree[cur].l+1);//c乘区间长 
        tree[cur].lazy+=c;//延迟标记 
        return ;
    }
    pushdown(cur);//修改节点区间 
    long long int mid=(tree[cur].l+tree[cur].r)>>1;//中间节点 
    if (L<=mid) up_date(L,R,c,tree[cur].ls);//递归修改左子区间 
    if (mid<R) up_date(L,R,c,tree[cur].rs);//右 
    pushup(cur); //更新节点区间 
}
int query(long long int L,long long int R,int cur)//单位置,查询区间和 ，拆分成单个数组 
{
    if (L<=tree[cur].l&&R>=tree[cur].r) return tree[cur].sum;//当前节点为待查询区间子集
    //否则 
    long long int tot=0;//求和 
    long long int mid=(tree[cur].l+tree[cur].r)>>1;//取中点 
    if (L<=mid) tot+=query(L,R,tree[cur].ls);//递归左端点的子集和 
    if (R>mid) tot+=query(L,R,tree[cur].rs);//递归右端点的子集和 
    return tot;//返回所有子集和 
}
long long int queryy(long long int L,long long int R,int cur)//整体区间 
{
    if (L<=tree[cur].l&&R>=tree[cur].r) return tree[cur].sum;//当前节点为待查询区间子集
    //否则 
    pushdown(cur);
    long long int tot=0;
    long long int mid=(tree[cur].l+tree[cur].r)>>1;//取中点 
    if (L<=mid) tot+=queryy(L,R,tree[cur].ls);//递归左端点的子集和 
    if (R>mid) tot+=queryy(L,R,tree[cur].rs);//递归右端点的子集和 
    return tot;//返回所有子集和 
} 
int main()
{
    scanf("%d %d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]); 
    }
    build(1,n,rt);//递归构树
    long long int t,b,s,d;
    while (m--)
    {
        scanf("%lld",&s);
        if (s==1)
        {
            scanf("%lld %lld %lld",&t,&b,&d);
            up_date(t,b,d,1);
        }
        else 
        {
            scanf("%lld %lld",&t,&b);
            printf("%lld\n",queryy(t,b,1));
        }
    } 
    return 0;
} 

模板2 的代码我暂时没有更新，小伙伴Andy写了，先看他的

我日后更新