线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。

例题

数列区间最大值

题目链接：https://www.acwing.com/problem/content/1272/
ST算法
思路分析：直接暴力求，明显的，最坏情况下时间复杂度为O(nm)=10^11，肯定超时
用ST算法来求，预处理O(nlogn)=10^7,查询O(m*1)=10 ^6不会超时
暴力超时代码：

#include
using namespace std;
const int N=100005;
int a[N];
int n,m,x,y;
int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;iscanf("%d %d",&x,&y);int max=0;for(int j=x;j<=y;j++){if(a[j]>max) max=a[j];}printf("%d\n",max);}return 0;
}

AC代码：

#include
using namespace std;
typedef long long LL;
const LL N=100005;
LL a[N];
LL n,m,x,y;
LL dp[N][20];  //2^20就足够大于n了//预处理
void ST()
{for(LL i=1;i<=n;i++) dp[i][0]=a[i];for(LL j=1;1<for(LL i=1;i+(1<dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}}
}
//查询
LL query(LL l,LL r)
{LL t=log2(r-l+1);return max(dp[l][t],dp[r-(1<scanf("%d %d",&n,&m);for(LL i=1;i<=n;i++)  scanf("%d",&a[i]);ST();while(m--){scanf("%d %d",&x,&y);printf("%d\n",query(x,y));}return 0;
}

线段树算法
思路分析：
AC代码：

最敏捷的机器人

题目链接：https://www.acwing.com/problem/content/description/1273/
思路分析：就维护最大值和最小值数组即可
AC代码：

#include
using namespace std;
const int N=100005;
typedef long long LL;
LL a[N];
LL Max[N][20];  // 最大值
LL Min[N][20];  //最小值
int n,k;
int main()
{scanf("%d %d",&n,&k);for(int i=1;i<=n;i++) {scanf("%ld",&a[i]);Max[i][0]=a[i];Min[i][0]=a[i];}for(int j=1;1<for(int i=1;i+(1<<(j-1))-1<=n;i++){Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);}}int t=n-k+1;for(int i=1;i<=t;i++){int l=i,r=i+k-1;int tmp=log2(k);printf("%d ",max(Max[l][tmp],Max[r-(1<

#include
#include
#include
using namespace std;
const int N=100005;
int a[N];
int dp[N][20];
int n,q,t,pre,x,y;
void ST()
{for(int i=1;i<=n;i++) dp[i][0]=a[i];for(int j=1;1<for(int i=1;i+(1<dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}}
} 
int query(int l,int r)
{t=log2(r-l+1);return max(dp[l][t],dp[r-(1<while(scanf("%d", &n) && n != 0){scanf("%d",&q);int pre=-100001;for(int i=1;i<=n;i++){scanf("%d",&t);if(t==pre) a[i]=a[i-1]+1;else a[i]=1;pre=t;}ST();while(q--){scanf("%d %d",&x,&y);int l=-1;for(int i=x;i<=y;i++){if(a[i]==1) {l=i;break;}  //找到第一个1作为区间左部 }if(l!=-1) printf("%d\n",max(l-x,query(l,y)));   //区间内有1 else printf("%d\n",y-x+1);      //区间内没有1 }}return 0;
}/*
10 41  2 3 4 5 6 7  8  9 10  //下标 
-1 -1 1 1 1 1 3 10 10 10  //所给数组 1  2 1 2 3 4 1 1  2  3   //连续标号后的数组 
2 3 --1     待求区间内只有一组连续重复值，前面有上一组剩下的一个元素 
1 10  -- 4  待求区间内有多组连续重复值，前面没有上一个组剩下的一些元素 
5 10  --3   待求区间内有多组连续重复值，前面有上一组剩下的两个元素
4 6   --3   待求区间内没有新的连续重复值，只有前面上一组剩下的元素 
0
*/