线段树例题

本文主要是介绍线段树例题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.Sequence

2.Peach Conference

3.Permutation Subsequence

---

1.Sequence

题目描述：

Given an array a consisting of n integers, on which you are to perform m operations of two types.

1.Given two integers x,y, replace the number of index x with number y. That is ax:=y.

2.Given one integer x, print the number of consecutive subsequences of a, whose minimum value equals to ax.

It's guaranteed that there are no duplicated value in array a at any moment.

输入描述：

The first line contains two intergers n,m(1≤n,m≤10^5)，where n is the size of the array and m is the number of operations to perform.

The second line contains n integer, the ith integer is ai (1≤ai≤2^31-1)

Then,m lines follow, describing m operation you are to perform in order.
Each line start with an integer opt∈[1,2], meaning the type of operation to perform.

If opt=1,two integers x, y (1≤x≤n,1≤y≤2^31-1) follows,mentioned above.

If opt=2,one integers x (1≤x≤n) follows, mentioned above.

输出描述：
For each operation of type 2, print one integer on one line as the answer.

输入样例：

10 5
8 3 6 2 10 9 5 7 1 4 
2 2
1 9 11
1 5 12
2 4
1 8 18

输出样例：

4
28

思路： 用线段树进行op=1的单点修改，用二分+区间查询进行op=2的查找Ax左边最后一个小于Ax的位置ans1，然后查找Ax右边第一个小于Ax的位置ans2，答案就是(x-ans1+1)*(ans2-x+1),这里的二分还是有许多细节需要注意，这里就不多说了，大家看代码理解吧

#include<iostream>
#include<limits.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,w[N];struct node{int l,r;int mind;
}tr[4*N];void pushup(int u)
{tr[u].mind=min(tr[u<<1].mind,tr[u<<1|1].mind);
}void build(int u,int l,int r)
{if(l==r)  tr[u]={l,l,w[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);}
}int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mind;else{int mid=(tr[u].l+tr[u].r)>>1;int v=INT64_MAX;if(mid>=l) v=min(query(u<<1,l,r),v);if(mid<r) v=min(v,query(u<<1|1,l,r));return v;}
}void modify(int u,int x,int y)
{if(tr[u].l==x&&tr[u].r==x) tr[u]={x,x,y};else{int mid=(tr[u].l+tr[u].r)>>1;if(mid>=x) modify(u<<1,x,y);else modify(u<<1|1,x,y);pushup(u);}
}int32_t main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);while(m--){int type;cin>>type;if(type==1){int x,y;cin>>x>>y;w[x]=y;modify(1,x,y);}else{int x;cin>>x;int a=w[x]; int l1=1,r1=x-1,ans1,ans2;while(l1<=r1)//先二分x的左边{int mid=(l1+r1+1)>>1;if(query(1,mid,x-1)<a) l1=mid+1;//如果mid~x-1这个区间存在比a更小的值，则区间向右边移动一个单位，缩小范围else r1=mid-1;//反之则扩大范围，向左边移动}ans1=l1;//取离x更近的值int l2=x+1,r2=n;while(l2<=r2)//二分x的右边{int mid=(r2+l2)>>1;if(query(1,x+1,mid)<a) r2=mid-1;//如果x+1~mid这个范围存在比a更小的值，则区间向左移动一个单位，缩小范围else l2=mid+1;//反之则扩大范围，向右边移动}ans2=r2;cout<<(x-ans1+1)*(ans2-x+1)<<endl;}}
}

2.Peach Conference

题目描述：

Sun Wukong was honored as the great saint of Qitian. He was very happy, so he held a peach meeting for the monkeys (ID numbered 1 to N). To make it more interesting, Sun Wukong decided to throw the dice. The conference will roll the dice Q times, forming Q instructions, each in the form of ’m a b’, where m is an integer label, and a and b are monkey’s ID. The meaning of each instruction is as follows:

1. If m > 0, send m peaches to each monkey in ID interval [a, b];

2. If m < 0, remove |m| peaches from each monkey in the ID interval [a, b] (if the number of peaches from any monkey is less than |m|, remove all peaches of the monkey);

3. If m = 0, calculate the sum of peaches of each monkey in the interval [a, b]; now you are invited to preside over the peach conference, can you complete the task according to the requirements of Sun Wukong?

输入描述：

The fifirst line contains two positive integers N and Q (1 ≤ N, Q ≤ 100000), representing N monkeys and Q instructions, respectively.

Next, there are Q lines, and each line corresponds to one instruction. Each instruction is composed of three integers m (−10000 ≤ m ≤ 10000), a and b (1 ≤ a ≤ b ≤ N), which respectively represent the label m and the ID interval of monkey.

输出描述：

Output each instruction with label m = 0 as an integer in order per line, that is, the sum of peaches of each monkey in the interval [a, b].

输入样例：

10 8
1 1 10
0 4 6
2 3 6
0 4 5
-2 5 8
0 4 7
-2 4 5
0 3 5

输出样例：

3
6
5
4

思路： 线段树+懒标记，如果在区间[l,r]中最小值减m会>=0，则不用进行标记，如果最大值减m<=0，则要进行标记，具体请看代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+5;int n,q,w[N];
struct node{int l,r;int sum,mind,maxd,add,clear;
}tr[4*N];void pushdown(int u)
{node &left=tr[u<<1],&right=tr[u<<1|1],&root=tr[u];if(root.clear){left.sum=left.mind=left.maxd=left.add=0;left.clear=1;right.sum=right.mind=right.maxd=right.add=0;right.clear=1;root.clear=0;}if(root.add){left.sum+=(left.r-left.l+1)*root.add;left.mind+=root.add,left.maxd+=root.add;left.add+=root.add;right.sum+=(right.r-right.l+1)*root.add;right.mind+=root.add,right.maxd+=root.add;right.add+=root.add;root.add=0;return ;}}void pushup(int u)
{tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;tr[u].maxd=max(tr[u<<1].maxd,tr[u<<1|1].maxd);tr[u].mind=min(tr[u<<1].mind,tr[u<<1|1].mind);}void Build(int u,int l,int r)
{if(l==r) tr[u]={l,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 l,int r,int d)
{if(tr[u].l>=l&&tr[u].r<=r) {if(tr[u].mind+d>=0){tr[u].sum+=(tr[u].r-tr[u].l+1)*d;tr[u].add+=d;tr[u].maxd+=d;tr[u].mind+=d;return ;}if(tr[u].maxd+d<=0){tr[u].sum=tr[u].mind=tr[u].maxd=tr[u].add=0;tr[u].clear=1;return ;}}pushdown(u);int mid=(tr[u].l+tr[u].r)>>1;if(mid>=l) modify(u<<1,l,r,d);if(mid<r) modify(u<<1|1,l,r,d);pushup(u);}int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;else{pushdown(u);int mid=(tr[u].l+tr[u].r)>>1;int v=0;if(mid>=l)  v=query(u<<1,l,r);if(mid<r) v+=query(u<<1|1,l,r);return v;}
}int32_t main()
{cin>>n>>q;Build(1,1,n);while(q--){int m,l,r;cin>>m>>l>>r;if(m==0) cout<<query(1,l,r)<<endl;else  modify(1,l,r,m);}
}

3.Permutation Subsequence

注意 ：要用线段树来优化找区间最值，不然会超时

代码：

#include<iostream>
#include<cmath>
using namespace std;
const int N=2e5+5;
int a[N],book[N],n,k;
struct node{int l, r;int maxd ,mind;
}tr[4*N];void pushup(int u)
{tr[u].maxd=max(tr[u<<1].maxd,tr[u<<1|1].maxd);tr[u].mind=min(tr[u<<1].mind,tr[u<<1|1].mind);
}void build(int u,int l,int r)
{if(l==r) tr[u]={l,l,book[l],book[l]};else {int mid=(l+r)>>1;tr[u]={l,r};build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}int query(int u,int l,int r,int type)
{if(tr[u].l>=l&&tr[u].r<=r) {if(type==1) return tr[u].mind;else return tr[u].maxd;}else{int mid=(tr[u].l+tr[u].r)>>1;if(type==1){int min_=0x3f3f3f3f;if(mid>=l) min_=query(u<<1,l,r,type);if(mid<r) min_=min(min_,query(u<<1|1,l,r,type));return min_;}else{int max_=0;if(mid>=l) max_=query(u<<1,l,r,type);if(mid<r) max_=max(max_,query(u<<1|1,l,r,type));return max_;}}
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++) {cin>>a[i];book[a[i]]=i;}int min_=0x3f3f3f3f;build(1,1,n);for(int i=1;i<=n-k+1;i++){int max_=query(1,i,i+k-1,2);int mi_=query(1,i,i+k-1,1);min_=min(min_,abs(max_-mi_));}cout<<min_;
}

这篇关于线段树例题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---