线段树1对于Pushdown的理解
线段树1是一个区间修改和区间求值的题，他相当于以前的线段树——区间求值和单点修改和区间修改和单点求值，产生了本质上的一些区别，最主要的就在于Pushdown上的区别，现在我们就来区分一下。
1、线段树练习——单点修改和区间求值
这个主要考察的就是线段树最主要的三个步骤 建树（Buildtree） 修改（modify） 查询（query）本题难度不大，就是让OIER们熟悉一下线段树这个数据结构。因此先介绍一下基本操作。
1、建树 （Buildtree）
void buildTree(int &k,int l,int r)
{
//初始化一个管理[l,r]的节点 ， 下标为k
k=++cnt;//k = cnt+1; cnt++;
node[k].l=l;node[k].r=r;//初始化[l,r]
if(l==r)
{
//没有儿子了
node[k].sum=ini[r];
}
else
{
//我是爸爸
int mid=( node[k].l+node[k].r )/2;//儿子的左右分界
buildTree(node[k].son[L],l,mid);//调用完后 左右儿子下表就可以被储存
buildTree(node[k].son[R],mid+1,r);
node[k].sum=node[ node[k].son[L] ].sum + node[ node[k].son[R] ].sum;//计算当前节点的和
}
}
2、修改（modify）
void modify(int k,int pos,int val)
{
//修改 把ini[pos]修改为val
if(node[k].l==node[k].r)
{
//儿子！ l==r l==pos
node[k].sum+=val;
ini[pos]+=val;//好像没有用
}
else
{
int mid=( node[k].l+node[k].r )/2;//儿子的左右分界
if( pos<=mid ) modify(node[k].son[L],pos,val);//这个点在左儿子
else modify(node[k].son[R],pos,val);
node[k].sum=node[ node[k].son[L] ].sum + node[ node[k].son[R] ].sum;//计算当前节点的和
}
}
3、查询（query）
long long query(int k,int ql,int qr)
{
//查询[ql,qr]☣
if(node[k].l==ql && node[k].r==qr)
{
return node[k].sum;
}
else
{
int mid=( node[k].l+node[k].r )/2;//儿子的左右分界
if(qr<=mid) return query(node[k].son[L],ql,qr);//全在左儿子
else if(ql>=mid+1) return query(node[k].son[R],ql,qr);//全在右儿子
else return query(node[k].son[L],ql,mid) + query(node[k].son[R],mid+1,qr);//分开了
}
}
请记住query查询一定要用“long long”
有了以上的帮助后，再加上自己对Pushdown的理解，于是luogu上的线段树1就已经可以干掉了。
代码如下：
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
struct sd{
int l,r,son[2];
long long add,sum;
}node[N*2];
int root,cnt=0;
int ini[N];
void Buildtree(int &k,int l,int r)
{
k=++cnt;
node[k].l=l;
node[k].r=r;
if(l==r)
{
node[k].sum=ini[l];
}
else
{
int mid=(l+r)/2;
Buildtree(node[k].son[0],l,mid);
Buildtree(node[k].son[1],mid+1,r);
node[k].sum=node[node[k].son[0]].sum+node[node[k].son[1]].sum;
}
}
void pushdown(int k)
{
node[node[k].son[0]].add+=node[k].add;
node[node[k].son[1]].add+=node[k].add;
node[node[k].son[0]].sum+=node[k].add*(node[node[k].son[0]].r-node[node[k].son[0]].l+1);
node[node[k].son[1]].sum+=node[k].add*(node[node[k].son[1]].r-node[node[k].son[1]].l+1);
node[k].add=0;//☣
}
void modify(int k,int ql,int qr,int val)
{
if(ql==node[k].l&&qr==node[k].r)
{
pushdown(k);
node[k].add+=val;
node[k].sum+=(node[k].r-node[k].l+1)*node[k].add;
}
else
{
pushdown(k);
int mid=(node[k].l+node[k].r)/2;
if(mid>=qr) modify(node[k].son[0],ql,qr,val);
else if(mid<ql) modify(node[k].son[1],ql,qr,val);
else
{
modify(node[k].son[0],ql,mid,val);
modify(node[k].son[1],mid+1,qr,val);
}
node[k].sum=node[node[k].son[0]].sum+node[node[k].son[1]].sum;
}
}
long long query(int k,int ql,int qr)
{
if(ql==node[k].l&&qr==node[k].r)
{
return node[k].sum;
}
else
{
pushdown(k);
int mid=(node[k].l+node[k].r)/2;
if(mid>=qr) return query(node[k].son[0],ql,qr);
else if(mid<ql) return query(node[k].son[1],ql,qr);
else
{
return query(node[k].son[0],ql,mid)+query(node[k].son[1],mid+1,qr);
}
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&ini[i]);
}
Buildtree(root,1,n+3);
int a,b,c,d;
for(int i=1;i<=m;++i)
{
scanf("%d",&d);
if(d==1)
{
scanf("%d%d%d",&a,&b,&c);
modify(root,a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%lld
",query(root,a,b));
}
}
return 0;
}
***Pushdown方面展示：***
void pushdown(int k)
{
node[node[k].son[0]].add+=node[k].add;
node[node[k].son[1]].add+=node[k].add;
node[node[k].son[0]].sum+=node[k].add*(node[node[k].son[0]].r-node[node[k].son[0]].l+1);
node[node[k].son[1]].sum+=node[k].add*(node[node[k].son[1]].r-node[node[k].son[1]].l+1);
node[k].add=0;
}
线段树2有一点耗脑力，需要后续思考！
后续持续更新······
这里有一个思路比较清晰的线段树：
#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
LL root,m,n,cnt=0,ini[N];
struct sd{
LL son[2],l,r,sum,add;
}node[N*3];
void update(LL k){node[k].sum=node[node[k].son[0]].sum+node[node[k].son[1]].sum;}
void add(LL k,LL val)
{
node[k].add+=val;
node[k].sum+=val*(node[k].r-node[k].l+1);
}
void pushdown(LL k)
{
add(node[k].son[0],node[k].add);
add(node[k].son[1],node[k].add);
node[k].add=0;
}
void Buildtree(LL &k,LL l,LL r)
{
cnt++;k=cnt;node[k].l=l;node[k].r=r;
if(l==r)node[k].sum=ini[l];
else
{
LL mid=(l+r)/2;
Buildtree(node[k].son[0],l,mid);
Buildtree(node[k].son[1],mid+1,r);
update(k);
}
}
void modify(LL k,LL l,LL r,LL val)
{
if(node[k].l==l&&node[k].r==r) add(k,val);
else
{
pushdown(k);
LL mid=(node[k].l+node[k].r)/2;
if(r<=mid) modify(node[k].son[0],l,r,val);
else if(l>mid) modify(node[k].son[1],l,r,val);
else modify(node[k].son[0],l,mid,val),modify(node[k].son[1],mid+1,r,val);
update(k);
}
}
LL query(LL k,LL l,LL r)
{
if(node[k].l==l&&node[k].r==r) return node[k].sum;
else
{
pushdown(k);
LL mid=(node[k].r+node[k].l)/2;
if(r<=mid) return query(node[k].son[0],l,r);
else if(l>mid) return query(node[k].son[1],l,r);
else return query(node[k].son[0],l,mid)+query(node[k].son[1],mid+1,r);
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&ini[i]);
Buildtree(root,1,n);LL a,b,c,d;
for(int i=1;i<=m;++i)
{
scanf("%lld%lld%lld",&a,&b,&c);
if(a==1) scanf("%lld",&d),modify(root,b,c,d);
if(a==2) printf("%lld
",query(root,b,c));
}
return 0;
}
指针版的线段树戳这里☞指针版的线段树