前言
线段树，维护区间修改的利器，种类繁多。以其码量巨大的特点骇人听闻。
\(OIerhhx\)为了让线段树的使用方便更加方便简洁，不再苦恼，于是写下了这篇博客。
线段树伪代码指南
这一部分主要是为了梳理线段树代码：减化码量，矫正易错。
/*important*/
线段树结构体
{
懒标记+其他信息
}
lson函数（用于遍历函数查询子区间）//简化码量
{
return (l+r)/2;
}
rson函数（用于遍历函数查询子区间）//简化码量
{
return (l+r)/2+1;
}
maketag函数(用于遍历函数修改tag)//简化码量
{
/*仅对于该修改对该节点的懒标计和其他信息*/
}
pushdown函数(用于遍历函数更新)//简化码量
{
/*用该节点tag修改子节点信息+清空tag*/
}
update函数(用于子节点回溯后更新父节点)//简化码量
{
子节点比较求值
}
建树函数
{
子区间：预处理+return
其他区间：预处理+update
}
遍历函数
{
在修改/查询区间内：修改信息（/*仅对于该修改对该节点的懒标计和其他信息*/）/统计信息+return
pushdown
与左子区间交集
递归
与右子区间交集
update
return
}
以P3372 【模板】线段树 1为例：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,m;
int a[N];
struct point{
int val,add,len;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x].val=tree[x*2].val+tree[x*2+1].val;
return;
}
void pushdown(int x)
{
tree[x*2].val+=tree[x].add*tree[x*2].len;
tree[x*2+1].val+=tree[x].add*tree[x*2+1].len;
tree[x*2].add+=tree[x].add;
tree[x*2+1].add+=tree[x].add;
tree[x].add=0;
return;
}
void make(int x,int to)
{
tree[x].val+=to*tree[x].len;
tree[x].add+=to;
return;
}
void build(int l,int r,int x)
{
tree[x].len=r-l+1;
if(l==r)
{
tree[x].val=a[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
void ad(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
make(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
ad(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
ad(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x].val;
}
pushdown(x);
int s=0;
if(lson(l,r)>=l1)
s+=get(l,lson(l,r),x*2,l1,r1);
if(rson(l,r)<=r1)
s+=get(rson(l,r),r,x*2+1,l1,r1);
update(x);
return s;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,n,1);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
ad(1,n,1,x,y,z);
}
else
{
int x,y;
cin>>x>>y;
cout<<get(1,n,1,x,y)<<'\n';
}
}
return 0;
}