首先声明一下，线段树做法对于本题而言无论是复杂度还是代码长度都劣于前缀和+dp做法。笔者也已经写了前缀和dp的题解：https://blog.nowcoder.net/n/1042c69bd06d40b98f69daf8f708b28b
之所以写线段树做法，一是因为自己的数据结构很弱，需要练习（本题的线段树调试的时候发现各种bug，说明不熟练Orz），二是给希望学习线段树的童鞋们一个参考，本题是个不错的练习对象，值得去写一下。
先介绍一下线段树。（已经掌握线段树的可以跳过）。
线段树是一棵用来表示数组的区间的二叉树，每一个节点都表示原数组中的一个区间。对于一个数组而言，二叉树的根代表 区间。对于每一个节点 ，如果它所对应的区间是 ，那么它的左儿子对应的区间为 ，右儿子对应的区间为 。
这个二叉树可以用数组进行表示。假设 代表根节点， 对于 节点而言，它的左节点是 ，右节点是 ，那么就可以用一个结构体数组存所有的节点了。
这种线段树的好处在于，可以在节点维护各种东西，例如区间和、区间最大值、区间gcd等等，这样在构建之后可以做到 查询。
对于本题而言，由于是取两个区间，在遍历左区间的位置时求右区间和的最大值，可以用线段树做到 查询，总复杂度 。
代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum[422222],a[422222];
struct stree{
    int p,l,r;
    ll ma;
};
stree t[800020];
void build(int p,int l,int r){        //递归建立线段树
    t[p].l=l,t[p].r=r;                //线段树的区间左端点和右端点赋值。
    if(l==r){t[p].ma=a[l];return;}
    int mid=l+r>>1;
    build(p*2,l,mid);                //递归左儿子
    build(p*2+1,mid+1,r);            //递归右儿子
    t[p].ma=max(t[2*p].ma,t[2*p+1].ma);    //区间最大值赋值。
}
ll ask(int p,int l,int r){    //在节点p对应区间找原数组里l到r的最大值
    if(t[p].l>=l&&t[p].r<=r)return t[p].ma;    //若p对应区间被包含在[l,r]区间里，则直接返回。
    int mid=t[p].l+t[p].r>>1;
    ll ma=-1e18;
    if(l<=mid)ma=max(ma,ask(p*2,l,r));    //递归找左节点
    if(r>mid)ma=max(ma,ask(p*2+1,l,r));    //递归找右节点
    return ma;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k,i,x;
        ll s=0;
        cin>>n>>k;
        for(i=1;i<=n;i++){
            scanf("%d",&x);
            s+=x;
            sum[i]=s;
        }
        for(i=1;i<=n-k+1;i++){
            a[i]=sum[i+k-1]-sum[i-1];
        }
        build(1,1,n-k+1);
        ll ma=-1e18;
        for(i=1;i<=n-2*k+1;i++){
            ma=max(ma,a[i]+ask(1,i+k,n-k+1));
        }
        cout<<ma<<endl;
    }
}