我尽然把一道dp的题用线段树写
nlogn的复杂度还被玄学的卡了一波常
建一棵求区间最大的线段树（我下面的线段树模板支持求区间和，区间最小，区间最大）
也可以自己传函数

用双指针法把每一个区间的值求出来扔进线段树中。

然后遍历每个区间，用当前区间的值加上后面区间的最大值看看能不能更新最大值。
比如说总共有5个区间那就进行如下操作
第1个区间的值+第2-5的区间最大值
第2个区间的值+第3-5的区间最大值
第3个区间的值+第4-5的区间最大值
第4个区间的值+第5-5的区间最大值

这段代码如果T了就多交几发，玄学

//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2e5;

namespace segment_tree
{
    //线段树模板
    template<class T>
    inline void sum_merge(T &a,T &b,T &c)
    {
        a=b+c;
    }

    template<class T>
    inline void sum_lazy_down(T &a,T &b,int n)
    {
        a+=b*n;
    }

    template<class T>
    inline T sum_ask_merge(T a,T b)
    {
        return a+b;
    }

    template<class T>
    inline void min_merge(T &a,T &b,T &c)
    {
        a=min(b,c);
    }

    template<class T>
    inline void min_lazy_down(T &a,T &b,int n)
    {
        a+=b;
    }

    template<class T>
    inline T min_ask_merge(T a,T b)
    {
        return min(a,b);
    }

    template<class T>
    inline void max_merge(T &a,T &b,T &c)
    {
        a=max(b,c);
    }

    template<class T>
    inline void max_lazy_down(T &a,T &b,int n)
    {
        a+=b;
    }

    template<class T>
    inline T max_ask_merge(T a,T b)
    {
        return max(a,b);
    }

    template<class T>
    struct tnode
    {
        T sum,lazy;
        int l,r;
    };

    template<class T>
    class Segment_Tree
    {
    public:
        void(*merge)(T &parent,T &child1,T &child2);//合并时的规则
        void(*lazy_down)(T &value,T &lazy_value,int segment_length);//懒标记下传时的规则
        T(*ask_merge)(T child1,T child2);//询问合并时的规则

        void sum_mode()
        {
            //求和模式
            merge=sum_merge;
            lazy_down=sum_lazy_down;
            ask_merge=sum_ask_merge;
        }

        void min_mode()
        {
            //求最小模式
            merge=min_merge;
            lazy_down=min_lazy_down;
            ask_merge=min_ask_merge;
        }

        void max_mode()
        {
            //求最大模式
            merge=max_merge;
            lazy_down=max_lazy_down;
            ask_merge=max_ask_merge;
        }


        void pushdown(int root)
        {
            //下传
            if(t[root].lazy!=0)
            {
                lazy_down(t[root].sum,t[root].lazy,t[root].r-t[root].l+1);
                if(t[root].l!=t[root].r)
                {
                    int ch=root<<1;
                    t[ch].lazy+=t[root].lazy;
                    t[ch+1].lazy+=t[root].lazy;
                }
                t[root].lazy=0;
            }
        }

        void update (int root)
        {
            //上更新
            int ch=root<<1;
            pushdown(ch);
            pushdown(ch+1);
            merge(t[root].sum,t[ch].sum,t[ch+1].sum);
        }

        void build(int l,int r,int root=1)
        {
            //建树
            t[root].l=l;
            t[root].r=r;
            t[root].sum=0;
            t[root].lazy=0;
            if(l!=r)
            {
                int mid=(l+r)>>1;
                int ch=root<<1;
                build(l,mid,ch);
                build(mid+1,r,ch+1);
                update(root);
            }
        }

        void change(int l,int r,T delta,int root=1)
        {
            if(l>r)
                return ;
            //区间修改
            if(l==t[root].l&&r==t[root].r)
            {
                t[root].lazy+=delta;
                pushdown(root);
                return;
            }
            int mid=(t[root].l+t[root].r)>>1;
            int ch=root<<1;
            if(r<=mid)
                change(l,r,delta,ch);
            else if(l>mid)
                change(l,r,delta,ch+1);
            else
            {
                change(l,mid,delta,ch);
                change(mid+1,r,delta,ch+1);
            }
            update(root);
        }

        T ask(int l,int r,int root=1)
        {
            if(l>r)
                return 0;
            //区间查询
            pushdown(root);
            if(t[root].l==l&&t[root].r==r)
            {
                return t[root].sum;
            }
            int mid=(t[root].l+t[root].r)>>1;
            int ch=root<<1;
            if(r<=mid)
                return ask(l,r,ch);
            else if(l>mid)
                return ask(l,r,ch+1);
            else
                return ask_merge(ask(l,mid,ch),ask(mid+1,r,ch+1));
        }

    private:
        tnode<T> t[4*MAXN];
    };   
}

//快读，不用就T被卡常了   
template<typename T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) //EOF
        return 0;
    while(c!='-'&&(c<'0'||c>'9'))
        c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9')
        ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
template<typename T>
inline void out(T x)
{
    if(x>9)
        out(x/10);
    putchar(x%10+'0');
}


using namespace segment_tree;
int a[MAXN];
int n,k;
Segment_Tree<ll> sg;
void solve()
{
    scan_d(n);
    scan_d(k);
    sg.build(1,n);
    for(int i=1;i<=n;i++)
    {
        scan_d(a[i]);
    }

    //双指针求每个区间的值，扔进线段树中
    ll tmp=0;
    for(int i=1;i<=k;i++)
        tmp+=a[i];
    sg.change(1,1,tmp);
    for(int i=2,j=k+1;j<=n;i++,j++)
    {
        tmp+=-a[i-1]+a[j];
        sg.change(i,i,tmp);
    }

    //这段没用，但是不写就T，我也不知道为什么，玄学
    for(int i=n-k+2;i<=n;i++)
        sg.change(i,i,0xcfcfcfcfcfcfcfcf);


    ll mx=0xcfcfcfcfcfcfcfcf;//注意负数
    for(int i=1;i+k+k-1<=n;i++)
    {
        tmp=sg.ask(i,i)+sg.ask(i+k,n-k+1);//当前区间+后面找最大的区间
        mx=max(mx,tmp);//看能不能更新最大值
    }
    printf("%lld\n",mx);
}

int main()
{
    sg.max_mode();//线段树调到区间最大模式
    int t;
    scan_d(t);
    while(t--)
        solve();
    return 0;
}