【数据结构】线段树算法介绍及模板代码
目录
1.核心思想
2.应用场景
3.单点修改线段树模板代码
4.区间修改线段树模板代码
线段树（Segment Tree）是一种高效处理区间查询和区间更新的数据结构，能在O(logn) 时间复杂度内完成区间操作。
1.核心思想
分治：将区间逐层二分，形成二叉树结构。
预处理与存储：预处理区间信息（如和、最大值），存储在每个节点中。
快速合并：通过子节点的信息合并得到父节点的信息。
2.应用场景
-
区间求和/求最大值最小值
-
区间赋值/区间增加
-
二维区间操作（如二维线段树）
-
动态规划优化（如RMQ问题）
3.单点修改线段树模板代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
int n;
const int maxn=50010;
int a[maxn*4];
struct node
{
int l,r,val;
};
node p[maxn*4];
void build(int ll,int rr,int rt)
{
p[rt].val=0;
p[rt].l=ll;
p[rt].r=rr;
if(ll==rr)
{
p[rt].val=a[ll];
return;
}
int mid=(ll+rr)/2;
build(ll,mid,2*rt);
build(mid+1,rr,2*rt+1);
p[rt].val=p[2*rt].val+p[2*rt+1].val;
}
void update(int tar,int val,int rt)
{
int l=p[rt].l;
int r=p[rt].r;
if(l==r)
{
p[rt].val+=val;
return;
}
int mid=(l+r)/2;
if(tar<=mid)
{
update(tar,val,2*rt);
}
else
{
update(tar,val,2*rt+1);
}
p[rt].val=p[2*rt].val+p[2*rt+1].val;
}
int query(int ll,int rr,int rt)
{
int l=p[rt].l;
int r=p[rt].r;
if(ll<=l&&rr>=r)
{
return p[rt].val;
}
int mid=(l+r)/2;
int res=0;
if(ll<=mid)
{
res+=query(ll,rr,2*rt);
}
if(rr>mid)
{
res+=query(ll,rr,2*rt+1);
}
return res;
}
int main()
{
int T;
int kase=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,n,1);
printf("Case %d:\n",kase++);
string s;
while(cin>>s)
{
if(s[0]=='Q')
{
int ll,rr;
scanf("%d%d",&ll,&rr);
int sum=query(ll,rr,1);
printf("%d\n",sum);
}
else if(s[0]=='A')
{
int po,c;
scanf("%d%d",&po,&c);
update(po,c,1);
}
else if(s[0]=='S')
{
int po,c;
scanf("%d%d",&po,&c);
update(po,-c,1);
}
else
{
break;
}
}
}
}
4.区间修改线段树模板代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
int n,m;
const int maxn=1e5+10;
int a[maxn*4];
struct node
{
int l,r,val;
int co;
};
node p[maxn*4];
void pushdown(int rt)
{
if(p[rt].co)
{
int sum1=p[rt*2].r-p[rt*2].l+1;
int sum2=p[rt*2+1].r-p[rt*2+1].l+1;
p[rt*2].co=p[rt].co;
p[rt*2+1].co=p[rt].co;
p[rt*2].val=sum1*p[rt].co;
p[rt*2+1].val=sum2*p[rt].co;
p[rt].co=0;
}
}
void build(int ll,int rr,int rt)
{
p[rt].co=0;
p[rt].l=ll;
p[rt].r=rr;
if(ll==rr)
{
p[rt].val=1;
return;
}
int mid=(ll+rr)/2;
build(ll,mid,2*rt);
build(mid+1,rr,2*rt+1);
p[rt].val=p[2*rt].val+p[2*rt+1].val;
//cout<<rt<<" "<<p[rt].val<<endl;
}
void update(int ll,int rr,int rt,int c)
{
int l=p[rt].l;
int r=p[rt].r;
if(ll<=l&&rr>=r)
{
p[rt].val=(r-l+1)*c;
p[rt].co=c;
return;
}
pushdown(rt);
int mid=(l+r)/2;
if(ll<=mid)
{
update(ll,rr,2*rt,c);
}
if(rr>mid)
{
update(ll,rr,2*rt+1,c);
}
p[rt].val=p[2*rt].val+p[2*rt+1].val;
}
int query(int ll,int rr,int rt)
{
int l=p[rt].l;
int r=p[rt].r;
if(ll>r||rr<l)
{
return 0;
}
if(ll<=l&&rr>=r)
{
return p[rt].val;
}
pushdown(rt);
int mid=(l+r)/2;
int res=0;
if(ll<=mid)
{
res+=query(ll,rr,2*rt);
}
if(rr>mid)
{
res+=query(ll,rr,2*rt+1);
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
int kase=1;
while(T--)
{
scanf("%d",&n);
build(1,n,1);
int q;
scanf("%d",&q);
while(q--)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
update(x,y,1,c);
}
int ans=p[1].val;
printf("Case %d: The total value of the hook is %d.\n",kase++,ans);
}
}