线段树2----简单拓展
通过之前的五个基本操作，可以组合出单点查询，单点修改，区间查询，区间修改等操作。
此外，线段树还可以与其他算法结合
目录
一、维护区间和，最大最小值
二、+差分求区间最大公约数
三、维护最长连续串 、最大连续子段和……
四、线段树优化dp
五、+扫描线
一、维护区间和，最大最小值
243. 一个简单的整数问题2 - AcWing题库 --- 区间和
struct node
{
int l,r;
ll sum,add;
}tr[N*4];知道子区间的和即可求出父区间的和，所以对于第二个操作只需要维护一个sum即可，add是懒标记，用来维护区间加操作，父区间的懒标记需要累加到子区间上。
//sum:如果考虑当前节点及子节点的所有标记，当前区间和是多少
//add:给当前区间的所有儿子加上add
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m;
int w[N];
struct node
{
int l,r;
ll sum,add;
}tr[N*4];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
auto &root=tr[u];
auto &left=tr[u<<1];
auto &right=tr[u<<1|1];
if(root.add)
{
left.add=left.add+root.add;
left.sum=left.sum+ll(left.r-left.l+1)*root.add;
right.add+=root.add;
right.sum+=ll(right.r-right.l+1)*root.add;
root.add=0;
}
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,r,w[r],0};
}
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int d)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
}
else//一定要分裂
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)
modify(u<<1,l,r,d);
if(r>mid)
modify(u<<1|1,l,r,d);
pushup(u);
}
}
ll query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
return tr[u].sum;
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
ll sum=0;
if(l<=mid)
sum=query(u<<1,l,r);
if(r>mid)
{
sum+=query(u<<1|1,l,r);
}
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
build(1,1,n);
char op[2];
int l,r,d;
while(m--)
{
scanf("%s%d%d",op,&l,&r);
if(*op=='C')
{
scanf("%d",&d);
modify(1,l,r,d);
}
else
printf("%lld\n",query(1,l,r));
}
return 0;
}
二、+差分求区间最大公约数
246. 区间最大公约数 - AcWing题库
利用更相减损术，可以推得
那么通过维护差分同样可以求最大公约数，且区间修改可以变为单点修改
struct node
{
int l,r;
ll sum;//差分前缀和
ll d;//最大公约数
}tr[N*4];/*此题核心为差分！！！！！！！！！！ */
//l-r同增一个数
/*修改一个数很简单,差分只需要改一个数*/
//最大公约数--->只需维护一个公约数--->扩展欧几里得算法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=500010;
typedef long long ll;
int n,m;
ll w[N];
struct node
{
int l,r;
ll sum;
ll d;//最大公约数
}tr[N*4];
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
void pushup(node &u,node &l,node &r)
{
u.sum=l.sum+r.sum;
u.d=gcd(l.d,r.d);
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void modify(int u,int x,ll v)
{
if(tr[u].l==x&&tr[u].r==x)
{
ll b=tr[u].sum+v;
tr[u]={x,x,b,b};
}
else
{
int mid=tr[u].l+tr[u].r >> 1;
if(x<=mid)
modify(u<<1,x,v);
else
modify(u<<1|1,x,v);
pushup(u);
}
}
node query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
return tr[u];
else
{
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid)
return query(u<<1,l,r);
else if(l>mid)
return query(u<<1|1,l,r);
else
{
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
node res;
pushup(res,left,right);
return res;
}
}
}
void build(int u,int l,int r)//维护差分
{
if(l==r)
{
ll b=w[r]-w[r-1];//维护差分
tr[u]={l,r,b,b};
}
else
{
tr[u].l=l,tr[u].r=r;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
build(1,1,n);
int l,r;
ll d;
char op[2];
while(m--)
{
scanf("%s%d%d",op,&l,&r);
if(*op=='Q')
{
auto left=query(1,1,l);
node right({0,0,0,0});
if(l+1<=r)
right=query(1,l+1,r);
printf("%lld\n",abs(gcd(left.sum,right.d)));
}
else
{
scanf("%lld",&d);
modify(1,l,d);
if(r+1<=n)
modify(1,r+1,-d);
}
}
return 0;
}三、维护最长连续串 、最大连续子段和……
245. 你能回答这些问题吗 - AcWing题库
维护一个最长连续的子段，对于一个区间来说，最长子段可能是最长前缀，可能是中间的一段，也可能是最长后缀。我们就需要维护这些性质：前缀、后缀，但是只维护这两个信息是不够的，因为最长前缀、最长后缀可能是跨整个子区间的，而前缀是不包含本身的，所以需要再维护一个区间和
struct node
{
int l,r;
int tmax;//最大子段和
int lmax;//最大前缀
int rmax;//最大后缀
int sum;
}tr[N*4];//直到所维护信息具有完备性//线段树
/*区间内最大子段和=max(完全处于左子区间，完全处于右子区间，横跨左右区间的最大字段和)*/
/*横跨左右子区间的最大字段和=
左子区间的最大后缀+右子区间的最大前缀*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=500010;
int n,m;
int w[N];
struct node
{
int l,r;
int tmax;
int lmax;
int rmax;
int sum;
}tr[N*4];//直到所维护信息具有完备性
void pushup(node&u,node&l,node&r)
{
//第一题中只需计算最大值v，而此题属性较多
u.sum=l.sum+r.sum;
u.lmax=max(l.lmax,l.sum+r.lmax);
u.rmax=max(r.rmax,r.sum+l.rmax);
u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if(l==r)
tr[u]={l,r,w[r],w[r],w[r],w[r]};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v)
{
if(tr[u].l==x&&tr[u].r==x)
tr[u]={x,x,v,v,v,v};
else
{
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid)
modify(u<<1,x,v);
else
modify(u<<1|1,x,v);
pushup(u);
}
}
node query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
else
{
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid)
return query(u<<1,l,r);
else if(l>mid)
return query(u<<1|1,l,r);
else
{
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
node res;
pushup(res,left,right);
return res;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
build(1,1,n);
int k,x,y;
while(m--)
{
scanf("%d%d%d",&k,&x,&y);
if(k==1)
{
if(x>y)
swap(x,y);
printf("%d\n",query(1,x,y).tmax);
}
else
modify(1,x,y);
}
return 0;
}四、线段树优化dp
295. 清理班次 - AcWing题库
这道题用贪心可以直接做出来，但可以作为线段树的练习题
我们用dp来解决这道题
状态表示：表示覆盖前 i 个班次的最小代价
状态转移方程：
在每次比较之后的值都可能会变，所以用线段树维护一下性质最小值
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 2500010;
const ll INF = 1e8;
struct seq
{
int l,r;
bool operator< (const seq &t) const
{
return r < t.r || (r == t.r && l < t.l);
}
}a[N];
struct node
{
int l,r;
ll minv;
}tr[N * 4];
ll f[N];
void pushup(int u)
{
tr[u].minv = min(tr[u << 1].minv,tr[u <<1|1].minv);
}
void build(int u,int l,int r)
{
if(l == r)
tr[u] = {l,r,f[l]};
else
{
tr[u] = {l,r};
int mid = l + r >> 1;
build(u << 1,l,mid),build(u<<1|1,mid + 1,r);
pushup(u);
}
}
void modify(int u,int x,ll v)
{
if(tr[u].l == tr[u].r)
{
tr[u].minv = v;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)
modify(u<<1,x,v);
else
modify(u<<1|1,x,v);
pushup(u);
}
ll query(int u,int l,int r)
{
if(tr[u].l >= l&&tr[u].r <= r)
return tr[u].minv;
int mid = tr[u].l + tr[u].r >> 1;
ll res = INF;
if(l <= mid)
res = min(res,query(u<<1,l,r));
if(r>mid)
res = min(res,query(u<<1|1,l,r));
return res;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i ++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].l = max(a[i].l,1);
a[i].r = min(a[i].r,m);
}
sort(a + 1,a + 1 + n);
for(int i = 0; i <= N;i ++)
f[i] = INF;
f[0] = 0;
build(1,0,m);
for(int i = 1; i <= n; i ++)
{
f[a[i].r] = min(f[a[i].r],query(1,a[i].l - 1,a[i].r)+1);
modify(1,a[i].r,f[a[i].r]);
}
if(f[m] == INF)
puts("-1");
else
printf("%lld\n",f[m]);
} 五、+扫描线
247. 亚特兰蒂斯 - AcWing题库
这道题运用了积分的思想，即将区间切分成非常多的长条，依据区间宽度有没有变化来判断，如下图：
将区间划分后，要想求全部的面积并，就等于求每个区间面积和，那么怎么求出每个区间的和呢？
首先我们处理一下这个图，对于所有的矩形，将它左边的线段标记为1，右边的线段标记为-1，如上图，然后从左往右做，如果遇到1，就会将它的纵坐标上的记录数值累加1，遇到-1，则-1。这就相当于把遇到的每个区间看成是一个操作。
然后处理每个线的时候，看一下当前线的累计值是多少，就是被几个矩形的宽覆盖。
覆盖长度 * 横坐标差值 = 区间面积
所以整个问题需要支持两个操作：
1.将某个区间[L,R] + k (k取0，1，-1）
2.求区间中长度大于0的区间总长，即矩形覆盖的范围
然后就可以用线段树来维护之前所说的纵坐标上记录的值，还需要维护一个当前区间被重复覆盖的次数，通过扫描线带有的性质优化，可以不需要懒标记
优化1：永远只考虑根节点的信息，这句话的意思是永远查询的是整个区间的信息，不会细分到子区间，query在第一次就会返回，不会递归
优化2：modify时也不需要pushdown，因为所有操作都是成对出现的，cnt 只有大于0和等于0的情况，如果大于0，不管是1，2，3……都只会被计算一次，所以不pushdown也没关系,如果等于0，那相当于没有懒标记，同样不需要pushdown
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100010;
int n;
struct segment//存储每个线段
{
double x,y1,y2;
int k;//权值是k
bool operator< (const segment &t)const
{
return x<t.x;
}
}seg[N*2];
struct node
{
int l,r;
int cnt;
double len;
}tr[N*8];
vector<double> ys;//离散化数组
int find(double y)
{
return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}
void pushup(int u)
{
if(tr[u].cnt)
tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
else if(tr[u].l!=tr[u].r)
{
tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}
else
tr[u].len=0;
}
void build(int u,int l,int r)
{
tr[u]={l,r,0,0};
if(l!=r)
{
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
}
void modify(int u,int l,int r,int k)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].cnt+=k;
pushup(u);
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)
modify(u<<1,l,r,k);
if(r>mid)
modify(u<<1|1,l,r,k);
pushup(u);
}
}
int main()
{
int t=1;
while(scanf("%d",&n),n)
{
ys.clear();
for(int i=0,j=0;i<n;i++)
{
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
seg[j++]={x1,y1,y2,1};
seg[j++]={x2,y1,y2,-1};
ys.push_back(y1),ys.push_back(y2);
}
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
build(1,0,ys.size()-2);//存的是区间
sort(seg,seg+n*2);
double res=0;
for(int i=0;i<n*2;i++)
{
if(i>0)
res+=tr[1].len*(seg[i].x-seg[i-1].x);
modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
}
printf("Test case #%d\n",t++);
printf("Total explored area: %.2lf\n\n",res);
}
}除了这些，线段树还有很多应用，比如二维线段树，可以对矩形区间内的性质进行维护，通常实现方法为线段树套线段树，而线段树还可以和平衡树等等结合使用，网上有很多博客进行了介绍