线段树 模板一题解

线段树模板题

虽然卡了我很久

大致思路就是建树->打懒惰标记->写查询和修改函数->按题意输出

AC代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
ll n,m;
ll arr[1000000];
struct node{
	ll l,r,w;
    ll lg;
	//左节点起始点，右节点终点 
};
node tree[1000000*4];//线段树开辟四倍空间 
void pushup(ll p){
    tree[p].w=tree[p*2].w+tree[p*2+1].w;
}
void js(ll p,ll l,ll r)
{
    tree[p].l=l;
    tree[p].r=r;
    if(l==r)
    {
        tree[p].w=arr[l];
        return ;
    }
    int mid=(l+r)/2;
    js(p*2,l,mid);
    js(p*2+1,mid+1,r);
    tree[p].w=tree[p*2].w+tree[p*2+1].w;
}

void lan(int p)
{
    if(tree[p].lg)
    {
        tree[p*2].w=tree[p*2].w+(tree[p*2].r-tree[p*2].l+1)*tree[p].lg;
        tree[p*2+1].w=tree[p*2+1].w+(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].lg;
        tree[p*2].lg=tree[p*2].lg+tree[p].lg;
        tree[p*2+1].lg=tree[p*2+1].lg+tree[p].lg;
        tree[p].lg=0;
    }
}
ll cx(ll p,int x,int y)
{
    if(x<=tree[p].l && y>=tree[p].r) 
    {
		return tree[p].w ;
	}
    lan(p);
	ll mid=(tree[p].l+tree[p].r) /2;
	long long flag=0;
	if(x<=mid){
		flag+=cx(p*2,x,y);//去左子树取值 
	}
	if(y>mid){
		flag+=cx(p*2+1,x,y);//去右子树取值 
	}
	return flag; 
}
void xg(ll p,ll x,ll y,ll z)
{
    if(x<=tree[p].l&&y>=tree[p].r)
    {
        tree[p].w+=(tree[p].r-tree[p].l+1)*z;
        tree[p].lg+=z;
        return ;
    }
    lan(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(x<=mid) xg(p*2,x,y,z);
    if(y>mid) xg(p*2+1,x,y,z);
    tree[p].w=tree[p*2].w+tree[p*2+1].w;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	js(1,1,n);
	for (int i=1;i<=m;i++)
	{
		char x;
		cin>>x;
		if(x=='1')
		{
			ll a,b,k;
			cin>>a>>b>>k;
			xg(1,a,b,k);
		}
        else
		{
			ll a,b;
			cin>>a>>b;
			cout<<cx(1,a,b)<<endl;
		}
	}
	return 0;
 }