数据结构菜鸟表示第一次见连续区间数据相互关联的题目。
难点:
1.线段树需要存储的数据,以及数据初始化
连续区间在某一线段树内的三种情况:挨着左边界,挨着右边界,在中间。
所以需要记录,从左边界起最大连续区间的和,在右边界结束的最大区间的和。
其中当前树范围【1-7】,计算【1-6】这一段左连续区间和 = 左子树的sum 【1-4】+右子树的左区间【5-6】
中间的情况可以拆分为,左子树的右连续区间最大和 + 右子树的左连续区间最大和 。
所以需要记录,左连续区间最大和,右连续区间最大和,当前树区间内的总和
2.如何查询
因为数据间有关联,不能像查询最大值一样递归到最后一层线段树求每一颗单独子树的贡献最后比出max。
例如【1-7】查询【4-5】,由于4,5在不在同一层线段树内,所以不能像设想一样执行
左子树的右连续区间最大和 + 右子树的左连续区间最大和
解决的方法是把每个子树的查询结果当成一颗线段树返回,由上层线段树类似pushup重新拼接回去计算答案。
好消息:
因为不存在区间修改,不需要lazy标记和update了。
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
inline int L(int r){return r << 1;}
inline int R(int r){return (r << 1) + 1;}
inline int MID(int l, int r){return (l + r) >> 1;}
const int max_n = 5e5 + 10;
//树的节点结构:线段的起点left和重点right
//[left, right]的和以及更新值lazy
struct node{
int left;
int right;
ll val, sum;
ll lmax, rmax;
}tree[max_n<<2];//interval tree
ll arr[max_n << 2];//init array
//建一棵树
void PushUp(int root){
tree[root].lmax = max(tree[L(root)].lmax, tree[L(root)].sum + tree[R(root)].lmax);
tree[root].rmax = max(tree[R(root)].rmax, tree[R(root)].sum + tree[L(root)].rmax);
tree[root].sum = tree[L(root)].sum + tree[R(root)].sum;
tree[root].val = max(tree[L(root)].val, tree[R(root)].val);
tree[root].val = max(tree[root].val, tree[L(root)].rmax + tree[R(root)].lmax);
}
void Built(int l, int r, int root)
{
tree[root].left = l;
tree[root].right = r;
if (l == r)
{
tree[root].sum = tree[root].val = tree[root].lmax = tree[root].rmax = arr[l];
return;
}
else
{
//递归构建左右子树
int mid = MID(l, r);
Built(l, mid, L(root));
Built(mid + 1, r, R(root));
//更新root
PushUp(root);
}
}
//加上v
void Add(int l, int r, ll v, int root)
{
if (l == tree[root].left && r == tree[root].right)
{
tree[root].sum = tree[root].val = tree[root].lmax = tree[root].rmax = v;
return;
}
else
{
//分别在左右子树上增加
int mid = MID(tree[root].left, tree[root].right);
if (l > mid)
Add(l, r, v, R(root));
else if (r <= mid)
Add(l, r, v, L(root));
PushUp(root);
}
}
node Solve(int l, int r, int root)
{
if (l == tree[root].left && r == tree[root].right)
{
return tree[root];
}
else {
int mid = MID(tree[root].left, tree[root].right);
if (l > mid)
return Solve(l, r, R(root));
else if (r <= mid)
return Solve(l, r, L(root));
else
{
node lt = Solve(l, mid, L(root));
node rt = Solve(mid + 1, r, R(root));
node ans;
ans.lmax = max(lt.lmax, lt.sum + rt.lmax);
ans.rmax = max(rt.rmax, rt.sum + lt.rmax);
ans.sum = lt.sum + rt.sum;
ans.val = max(lt.val, rt.val);
ans.val = max(ans.val, lt.rmax + rt.lmax);
return ans;
}
}
}
int main()
{
int m, n;
while (scanf("%d %d", &m, &n) != EOF)
{
for (int i = 1; i <= m; ++i)
scanf("%lld", arr + i);
//建树
Built(1, m, 1);
int op, l, r;
while (n--)
{
scanf("%d%d%d",&op,&l,&r);
if (op == 2)
{
Add(l, l, r, 1);
}
else
{
if(l > r)swap(l, r);
node ans = Solve(l, r, 1);
printf("%lld\n", ans.val);
}
}
}
}