- BC20260025's blog
10.15信息笔记（线段树1）
-
BC20260025
LV 6
@
2024-10-15 8:58:14
线段树1
基本概念
线段树是一棵二叉树，每个结点对应原序列的一段区间。
应用示例
给定序列，接下来有m次操作：单点修改或区间查询最小值。
算法：建树、查询、更新
示例：洛谷P3374（树状数组模板）
代码
# include<iostream>
using namespace std;
# define ll long long
const int N=5e5+2;
int n,m,op,x,y;
ll a[N],k,t[4*N];
void build(int l,int r,int i){
if(l==r) t[i]=a[l];
else{
int mid=(l+r)/2;
build(l,mid,2*i);
build(mid+1,r,2*i+1);
t[i]=t[2*i]+t[2*i+1];
}
}
void update(int l,int r,int i,int x,ll k){
if(x<l||r<x) return;
if(l==r){
a[x]+=k;
t[i]+=k;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(l,mid,2*i,x,k);
else update(mid+1,r,2*i+1,x,k);
t[i]+=k;
}//区间[l,r]编号为i，将a[x]加k
ll sum(int l,int r,int i,int x,int y){
if(x<=l&&r<=y) return t[i]; //[l,r]包含于[x,y]
if(y<l||r<x) return 0; //[l,r]与[x,y]无交集
int mid=(l+r)/2;
ll ans=0;
if(x<=mid) ans+=sum(l,mid,2*i,x,y); //[x,y]与[l,mid]有交集
if(mid<y) ans+=sum(mid+1,r,2*i+1,x,y); //[x,y]与[mid+1,r]有交集
return ans;
}//区间[l,r]编号为i，查询区间[x,y]
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
while(m--){
cin>>op;
if(op-1){
cin>>x>>y;
cout<<sum(1,n,1,x,y)<<endl;
}
else{
cin>>x>>k;
update(1,n,1,x,k);
}
}
return 0;
}
练习
- 提高P129
思路：维护一个长为 的线段树，A 操作就在末尾单点修改，Q 操作就区间查询。
代码
# include<iostream>
using namespace std;
const int M=2e5+2;
char op;
int m,p,n,ans=0,l,ma[4*M];
void update(int l,int r,int i,int x,int k){
if(l==r&&l==x){
ma[i]=max(ma[i],k);
return;
}
int mid=(l+r)/2;
if(x<=mid) update(l,mid,2*i,x,k);
if(mid<x) update(mid+1,r,2*i+1,x,k);
ma[i]=max(ma[2*i],ma[2*i+1]);
}
int find(int l,int r,int i,int x,int y){
if(x<=l&&r<=y) return ma[i];
int mid=(l+r)/2,ans=0;
if(x<=mid) ans=max(ans,find(l,mid,2*i,x,y));
if(mid<y) ans=max(ans,find(mid+1,r,2*i+1,x,y));
return ans;
}
int main(){
cin>>m>>p;
for(int i=1;i<=m;++i){
cin>>op>>l;
if(op=='A')
update(1,m,1,++n,(l+ans)%p);
if(op=='Q'){
ans=find(1,m,1,n-l+1,n);
cout<<ans<<endl;
}
}
return 0;
}
- 数据加强：洛谷P1198
代码
# include<iostream>
using namespace std;
# define ll long long
const int M=2e5+2;
char op;
int m,n,l;
ll p,ans,t,ma[4*M];
void update(int l,int r,int i,int x,ll k){
if(l==r&&l==x){
ma[i]=max(ma[i],k);
return;
}
int mid=(l+r)/2;
if(x<=mid) update(l,mid,2*i,x,k);
if(mid<x) update(mid+1,r,2*i+1,x,k);
ma[i]=max(ma[2*i],ma[2*i+1]);
}
int find(int l,int r,int i,int x,int y){
if(x<=l&&r<=y) return ma[i];
int mid=(l+r)/2,ans=0;
if(x<=mid) ans=max(ans,find(l,mid,2*i,x,y));
if(mid<y) ans=max(ans,find(mid+1,r,2*i+1,x,y));
return ans;
}
int main(){
cin>>m>>p;
for(int i=1;i<=m;++i){
cin>>op;
if(op=='A'){
cin>>t;
update(1,m,1,++n,(t+ans)%p);
}
if(op=='Q'){
cin>>l;
ans=find(1,m,1,n-l+1,n);
cout<<ans<<endl;
}
}
return 0;
}
- 洛谷P4588 数学计算
思路：类似上题，维护一个线段树，存储所有操作的乘积，每次执行操作 就更新线段树的末尾，每次执行操作 就将对应位置修改为 ，最后输出 就是答案。注意：一定要开 long long，否则会爆零！
代码
# include<iostream>
using namespace std;
# define ll long long
const int N=1e5+2;
int T,q,n,op,pos,a[N];
ll M,m,t[4*N];
void update(int l,int r,int i,int x,int k){
if(l==x&&r==x){
t[i]=k;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(l,mid,2*i,x,k);
if(mid<x) update(mid+1,r,2*i+1,x,k);
t[i]=t[2*i]*t[2*i+1]%M;
} //将a[x]修改为k
void solve(){
cin>>q>>M;
n=0;
for(int i=1;i<=4*q;++i) t[i]=1;
for(int i=1;i<=q;++i){
cin>>op;
if(op==1){
cin>>m;
a[i]=(++n);
update(1,q,1,n,m);
cout<<t[1]<<endl;
}
else{
cin>>pos;
update(1,q,1,a[pos],1);
cout<<t[1]<<endl;
}
}
}
int main(){
cin>>T;
while(T--) solve();
return 0;
}
- 洛谷P3801 红色的幻想乡
思路：维护两棵线段树，分别存储行和列中有多少是红雾，对于每个操作 ，利用容斥原理计算答案。记得开 long long！
代码
# include<iostream>
using namespace std;
# define ll long long
const int N=1e5+2;
int n,m,q,op,s,t,x1,y1,x2,y2;
int row[4*N],col[4*N];
void update(int* a,int l,int r,int i,int x){
if(l==x&&r==x){
a[i]^=1;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(a,l,mid,2*i,x);
if(mid<x) update(a,mid+1,r,2*i+1,x);
a[i]=a[2*i]+a[2*i+1];
}
int find(int* a,int l,int r,int i,int x,int y){
if(x<=l&&r<=y) return a[i];
int mid=(l+r)/2,ans=0;
if(x<=mid) ans+=find(a,l,mid,2*i,x,y);
if(mid<y) ans+=find(a,mid+1,r,2*i+1,x,y);
return ans;
}
int main(){
cin>>n>>m>>q;
while(q--){
cin>>op;
if(op==1){
cin>>s>>t;
update(row,1,n,1,s);
update(col,1,m,1,t);
}
else{
cin>>x1>>y1>>x2>>y2;
s=find(row,1,n,1,x1,x2);
t=find(col,1,m,1,y1,y2);
cout<<(ll)s*(y2-y1+1)+(ll)t*(x2-x1+1)-s*t*2<<endl;
}
}
return 0;
}