洛谷1714线段树加前缀和_在前缀和上的线段树

题目传送门：https://www.luogu.org/problemnew/show/P1714

题意很简单，在一段长度为n的序列里找出长度小于k的一段连续序列的最大值，是线段树无疑了。但是假如写一个求区间和的线段树你的复杂度大概为o（n^2logn），你要研究（1，k），（1，k-1）……（1,1,）中的最大值然后将以上操作重复n遍（严格来说没有n遍因为从n出发后只有（n，n），但无伤大雅，对于N≤500000肯定是gg的），那么我们想到没有学线段树的时候第一次听到求区间和的时候我第一个想到的是前缀和（因为当时没有引入维护），那么这个题也可以利用前缀和。将a数组利用前缀和维护之后，我要求的变成了（a[i]-a[i-1]），（a[i]-a[i-2]）……（a[i]-a[i-k+1]）时的最大值，那么我们用线段树维护a[i-1]到a[i-k+1]时的最小值即可，时间复杂度（nlogn），附上代码：

#include<stdio.h>
#include<stdlib.h>
struct seg{
    int val;
}seg[2000010];
int n,k;
int a[1000001]={0};
int max=-10000000;
int min(int x,int y)
{
    if(x>y)
      return y;
    else return x;
}
int quire(int root,int nstart,int nend,int qstart,int qend)
{
    int mid;
    if(nstart>qend||qstart>nend)
      return 100000000;
    if(nstart>=qstart&&nend<=qend)
      return seg[root].val;
    mid=(nstart+nend)/2;
    return min(quire(root*2,nstart,mid,qstart,qend),quire(root*2+1,mid+1,nend,qstart,qend));
}
int build(int root,int istart,int iend)
{
    int mid;
    if(istart==iend)
      {
      seg[root].val=a[istart];
      return 0;
      }
    mid=(istart+iend)/2;
    build(root*2,istart,mid);
    build(root*2+1,mid+1,iend);
    seg[root].val=min(seg[root*2].val,seg[root*2+1].val);
    return 0;
}
int main()
{
    int i;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
      scanf("%d",&a[i]);
      a[i]+=a[i-1];
    }
    build(1,1,n);
    for(i=1;i<=n;i++)
    {
    if(i-k>=1)
     {
      if(a[i]-quire(1,1,n,i-k,i)>max)
      max=a[i]-quire(1,1,n,i-k,i);
     }
    else if(a[i]-quire(1,1,n,1,i)>max)
      max=a[i]-quire(1,1,n,1,i);
    }
    printf("%d",max);
    return 0;
}