线段树基础与例题 本文章基本只提供模板，建议参考下(https://oi-wiki.org/ds/segment/)，里面有详细解释。 1.建树 ： 2.单点的添加（修改）： 3.区间查询： 4.区间修改（带懒惰标记）（下面代码为区间加上某个值，若是区间全部修改为某个值则把代码中+=全改为=即可）： 5.区间查询（带懒惰标记）（下面代码为区间修改时加上某个值，若是修改时区间全部修改为某个值则把代码中除了sum后面的+=全改为=即可）： 例题：
目录
F.HDU-4027 Can you answer these queries?
预处理（纯属为了写代码方便，线段树要多次用到这三个，每个代码前面带着这段就ok了）：
#define lson l,m,p<<1
#define rson m+1,r,p<<1|1
void pushplus(int p)
{
a[p] = a[p<<1] + a [p<<1|1]; //即a[p]=a[p*2]+a[p*2+1]
}1.建树 ：
void build(int l, int r, int p) {
// 对 [l,r] 区间建树,当前根的编号为 p
if (l == r) {
cin>>a[p];
return;
}
int m = (s + t) >> 1;
build(lson), build(rson);
// 递归对左右区间建树
pushplus(p)2.单点的添加（修改）：
void update(int x,int y,int l,int r,int p) //把x节点增加y（修改为y）
{
if(l==r){
a[p]+=y; //若是修改这段换成a[p]=y;
return ;
}
int m=(l+r)>>1;
if(x<=m)
update(x,y,lson);
else
update(x,y,rson);
pushplus(p);
}3.区间查询：
int query(int x,int y,int l,int r,int p)
{
if(x<=l&&r<=y)
return a[p];
int m=(l+r)>>1;
int sum=0;
if(x<=m)
sum+=query(x,y,lson);
if(y>m)
sum+=query(x,y,rson);
return sum;
}4.区间修改（带懒惰标记）（下面代码为区间加上某个值，若是区间全部修改为某个值则把代码中+=全改为=即可）：
void update(int l, int r, int c, int s, int t, int p) {
// [l,r] 为修改区间,c 为被修改的元素的变化量,[s,t] 为当前节点包含的区间,p
// 为当前节点的编号
if (l <= s && t <= r) {
a[p] += (t - s + 1) * c, b[p] += c;
return;
} // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
int m = (s + t) / 2;
if (b[p] && s != t) {
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
a[p * 2] += b[p] * (m - s + 1), a[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
if (l <= m) update(l, r, c, s, m, p * 2);
if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
pushplus(p);
}5.区间查询（带懒惰标记）（下面代码为区间修改时加上某个值，若是修改时区间全部修改为某个值则把代码中除了sum后面的+=全改为=即可）：
int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为修改区间,c 为被修改的元素的变化量,[s,t] 为当前节点包含的区间,p
// 为当前节点的编号
if (l <= s && t <= r) return d[p];
// 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2;
if (b[p]) {
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
a[p * 2] += b[p] * (m - s + 1), a[p * 2 + 1] += b[p] * (t - m),
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
int sum = 0;
if (l <= m) sum += getsum(l, r, s, m, p * 2);
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
return sum;
}例题：
A.HDU-1166 敌兵布阵：简单的单点模板题，AC题解：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#define M 50005
#define ll long long
#define lson l,m,p<<1
#define rson m+1,r,p<<1|1
using namespace std;
const int maxn = 1e6+10;
const int INF=0xfffffff;
int a[M<<2];
void pushplus(int rt)
{
a[rt] = a[rt<<1] + a [rt<<1|1];
}
void buide(int l,int r,int p)
{
if(l==r){
scanf("%d",&a[p]);
return ;
}
int m=(l+r)>>1;
buide(lson);
buide(rson);
pushplus(p);
}
void update(int x,int y,int l,int r,int p)
{
if(l==r){
a[p]+=y;
return ;
}
int m=(l+r)>>1;
if(x<=m)
update(x,y,lson);
else
update(x,y,rson);
pushplus(p);
}
int query(int x,int y,int l,int r,int p)
{
if(x<=l&&r<=y)
return a[p];
int m=(l+r)>>1;
int sum=0;
if(x<=m)
sum+=query(x,y,lson);
if(y>m)
sum+=query(x,y,rson);
return sum;
}
int main()
{
int t,x,y;
int T=1;
cin>>t;
while(t--){
printf("Case %d:
",T++);
int n;
cin>>n;
buide(1,n,1);
char str[20];
while(cin>>str&&str[0]!='E'){
cin>>x>>y;
if(str[0]=='A')
update(x,y,1,n,1);
else if(str[0]=='S')
update(x,-y,1,n,1);
else if(str[0]=='Q'){
cout<<query(x,y,1,n,1)<<endl;
}
}
}
return 0;
}B.HDU-1754 I Hate It:只需更换下父节点与子节点的关系即（a[p] = max(a[p<<1] , a [p<<1|1]),AC题解：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#define M 50005
#define ll long long
#define lson l,m,p<<1
#define rson m+1,r,p<<1|1
using namespace std;
const int maxn = 1e6+10;
const int INF=0xfffffff;
const int maxx=200005;
int a[maxx*4];
void pushplus(int rt)
{
a[rt] = max(a[rt<<1] , a [rt<<1|1]);
}
void build(int l,int r,int p)
{
if(l==r)
{
scanf("%d",&a[p]);
return ;
}
int mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
pushplus(p);
}
void update(int x,int y,int l,int r,int p)
{
if(l==r){
a[p]=y;
return ;
}
int m=(l+r)>>1;
if(x<=m)
update(x,y,lson);
else
update(x,y,rson);
pushplus(p);
}
int query(int x,int y,int l,int r,int p)
{
if(x<=l&&r<=y)
return a[p];
int m=(l+r)>>1;
int sum=0;
if(x<=m)
sum=max(query(x,y,lson),sum);
if(y>m)
sum=max(query(x,y,rson),sum);
return sum;
}
int main()
{
int n,t,x,y;
while(scanf("%d%d",&n,&t)!=EOF){
build(1,n,1);
while(t--){
char str;
scanf(" %c %d %d",&str,&x,&y);
if(str=='U')
update(x,y,1,n,1);
else
printf("%d
",query(x,y,1,n,1));
}
}
return 0;
}C.HDU-1698 Just a Hook：区间修改的模板题，只需注意数据类型即可，AC题解：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#define M 50005
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const long long maxn = 2e5+5;
const int INF=0xfffffff;
const int maxx=200005;
long long sum[maxx<<2],ad[maxx<<2];
void pushup(long long rt)
{
sum[rt] = sum[rt<<1] + sum [rt<<1|1];
}
void build(long long l,long long r,long long rt)
{
ad[rt]=0;
if(l==r)
{
sum[rt]=1;
return ;
}
long long m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(long long L,long long R,long long c,long long l,long long r,long long rt)
{
if(L<=l&&R>=r){
ad[rt]=c;
sum[rt]=(r-l+1)*c;
return ;
}
long long m=(l+r)>>1;
if(ad[rt]){
sum[rt*2]=ad[rt]*(m-l+1); sum[rt*2+1]=ad[rt]*(r-m);
ad[rt*2]=ad[rt]; ad[rt*2+1]=ad[rt];
ad[rt]=0;
}
if(L<=m)
update(L,R,c,lson);
if(R>m)
update(L,R,c,rson);
pushup(rt);
}
int main()
{
int kase=0;
long long q,n,t,c,x,y;
cin>>t;
while(t--){
cin>>n>>q;
build(1,n,1);
while(q--){
scanf("%lld %lld %lld",&x,&y,&c);
update(x,y,c,1,n,1);
}
printf("Case %d: The total value of the hook is %d.
",++kase , sum[1]);
}
return 0;
}D.ZOJ-1601 Count the Colors：区间染色问题，AC题解：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#define M 50005
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const long long maxn = 2e5+5;
const int INF=0xfffffff;
const int maxx=200005;
long long num[maxx<<2],ad[maxx<<2];
int nad;
void update(long long L,long long R,long long c,long long l,long long r,long long rt)
{
if(L<=l&&R>=r){
ad[rt]=c;
return ;
}
long long m=(l+r)>>1;
if(ad[rt]!=-1){
ad[rt*2]=ad[rt]; ad[rt*2+1]=ad[rt];
ad[rt]=-1;
}
if(L<=m)
update(L,R,c,lson);
if(R>m)
update(L,R,c,rson);
}
void query(long long l,long long r,long long rt)
{
if(l==r){
if(ad[rt]>=0&&ad[rt]!=nad)
num[ad[rt]]++;
nad=ad[rt];
return ;
}
long long m=(l+r)>>1;
if(ad[rt]!=-1){
ad[rt*2]=ad[rt]; ad[rt*2+1]=ad[rt];
ad[rt]=-1;
}
query(lson);
query(rson);
}
int main()
{
long long n,x,y,c;
while(scanf("%lld",&n)!=-1){
nad=-1;
memset(num,0,sizeof(num));
memset(ad,-1,sizeof(ad));
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&x,&y,&c);
if(x<y)
update(x+1,y,c,1,8000,1);
}
query(1,8000,1);
for(int i=0;i<=8000;i++){
if(num[i]) printf("%d %lld
",i,num[i]);
}
printf("
");
}
return 0;
}E.POJ-3264 Balanced Lineup:基础模板题，AC题解：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#define M 50005
#define ll long long
#define lson l,m,p<<1
#define rson m+1,r,p<<1|1
using namespace std;
const int maxn = 1e6+10;
const int INF=0xfffffff;
const int maxx=200005;
int a[maxx*4],b[maxx*4];
void pushplus(int rt)
{
a[rt] = max(a[rt<<1] , a [rt<<1|1]);
}
void pushplus1(int rt)
{
b[rt] = min(b[rt<<1] , b [rt<<1|1]);
}
void build(int l,int r,int p)
{
if(l==r)
{
scanf("%d",&a[p]);
b[p]=a[p];
return ;
}
int mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
pushplus(p);
pushplus1(p);
}
int query(int x,int y,int l,int r,int p)
{
if(x<=l&&r<=y)
return a[p];
int m=(l+r)>>1;
int sum=0;
if(x<=m)
sum=max(query(x,y,lson),sum);
if(y>m)
sum=max(query(x,y,rson),sum);
return sum;
}
int query1(int x,int y,int l,int r,int p)
{
if(x<=l&&r<=y)
return b[p];
int m=(l+r)>>1;
int sum=INF;
if(x<=m)
sum=min(query1(x,y,lson),sum);
if(y>m)
sum=min(query1(x,y,rson),sum);
return sum;
}
int main()
{
int n,m,x,y;
scanf("%d%d",&n,&m);
build(1,n,1);
while(m--){
scanf("%d %d",&x,&y);
printf("%d
",query(x,y,1,n,1)-query1(x,y,1,n,1));
}
return 0;
}F.HDU-4027 Can you answer these queries? ：本题需要一点优化技巧。在进行更新操作的时候，由于是开根号取整，1开根号是其本身，所以在每个子区间进行更新时，特判一下会快很多(这个优化非常重要)，避免超时。AC题解：
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=1e5+5;
typedef long long ll;
ll sum[maxn<<2];
void PushUP(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
if(l==r)
{
scanf("%lld",&sum[rt]);
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUP(rt);
}
void update(int L,int R,int l,int r,int rt)
{
if(l==r)
{
sum[rt]=sqrt(sum[rt]);
return ;
}
if(L<=l&&R>=r&&sum[rt]==r-l+1)//如果区间内的所有数都是1则不必更新
return;
int m=(l+r)>>1;
if(L<=m)
update(L,R,lson);
if(m<R)
update(L,R,rson);
PushUP(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int m=(l+r)>>1;
ll ret=0;
if(L<=m)
ret+=query(L,R,lson);
if(R>m)
ret+=query(L,R,rson);
return ret;
}
int main()
{
int n,m,t=0;
while(scanf("%d",&n)==1)
{
int a,b,c;
build(1,n,1);
scanf("%d",&m);
printf("Case #%d:
",++t);
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
if(b>c) swap(b,c);
if(a)
printf("%lld
",query(b,c,1,n,1));
else
update(b,c,1,n,1);
}
printf("
");
}
return 0;
}