目录
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);}
}
