《你能回答这些问题吗》线段树求区间最大连续子段和

本文主要是介绍《你能回答这些问题吗》线段树求区间最大连续子段和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

你能回答这些问题吗

《算法竞赛进阶指南》

给定长度为 $N$ 的数列 $A$ ，以及 $M$ 条指令，每条指令可能是以下两种之一：

1 x y，查询区间 $[x, y]$ 中的最大连续子段和，即 $max_{x≤l≤r≤y}{∑_{i=l}^r[i]}$
2 x y，把 $A [x]$ 改成 $y$ 。

对于每个查询指令，输出一个整数表示答案。

输入格式

第一行两个整数 $N, M$ 。

第二行 $N$ 个整数 $A [i]$ 。

接下来 $M$ 行每行 $3$ 个整数 $k, x, y$ ， $k = 1$ 表示查询（此时如果 $x > y$ ，请交换 $x, y$ ）， $k = 2$ 表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

$N \leq 500000, M \leq 100000$
$- 1000 \leq A [i] \leq 1000$

输入样例：

输出样例：

2
-1


/*线段树*/#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 5e5+5;
struct Node{int l,r;//左右边界int tmax; //区间最大连续子段和int lmax; //区间最大前缀和int rmax; //区间最大后缀和int sum; //区间和 
}tr[maxn*4]; int w[maxn];//存储初始值
int n, m;void pushup(Node& root,Node& l,Node& r)
{//区间和root.sum = l.sum + r.sum; //等于左右区间的和相加//区间最大前缀和root.lmax = std::max(l.lmax,l.sum+r.lmax); //左区间的最大前缀和 与 左边的和+右区间最大前缀和的最大值//区间最大后缀和root.rmax = std::max(r.rmax,r.sum+l.rmax);  //原理同上//区间最大连续子段和 root.tmax = std::max(std::max(l.tmax,r.tmax),l.rmax+r.lmax); //max{左区间的最大连续子段和 , 右区间的最大连续子段和 , 左区间的最大后缀和+ 右区间的最大前缀和}
}void pushup(int u)
{pushup(tr[u] , tr[u<<1], tr[u<<1|1]); //调用上面的函数
}//构建线段树 
void build(int u,int l,int r)
{if(l == r) tr[u] = {l,r,w[r],w[r],w[r],w[r]}; else {tr[u].l = l , tr[u].r = 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 x,int v)
{if(tr[u].l == x && tr[u].r == x) {tr[u] = {x,x,v,v,v,v};return;}int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);
}//查询
Node query(int u,int l,int r)
{if(l <= tr[u].l && tr[u].r <= r) //树中区间return tr[u]; int mid = tr[u].l + tr[u].r >> 1;if(r<=mid)  //右区间return query(u<<1,l,r);if(l > mid) //左区间return query(u<<1|1,l,r);if(l <= mid && r > mid) //跨区间{Node left = query(u<<1,l,r);Node right = query(u<<1|1,l,r);Node res;pushup(res,left,right);return res;}
}int main()
{int k,x,y;scanf("%d%d", &n, &m);for(int i=1;i<=n;++i) scanf("%d",&w[i]);build(1,1,n);while(m--){scanf("%d%d%d",&k,&x,&y);if(k == 1){if(x > y) std::swap(x,y);printf("%d\n",query(1,x,y).tmax);}else{modify(1,x,y);}}return 0;
}