C. 【例题3】公园遛狗
我们对于每一个线段树的节点，维护几个值
\(sum\) 表示当前区间的区间和
\(ml\) 表示最大前缀和
\(mr\) 表示最大后缀和
\(ans\) 表示当前区间的最大子段和
接下来我们来判断如何上传答案
首先假定 \(tr_{ls}\) 和 \(tr_{rs}\) 已经做好了，然后考虑合并成 \(tr_p\) 的值
首先 \(tr_p.sum=tr_{ls}.sum+tr_{rs}.sum\) 这个就是直接合并大区间
然后 \(tr_p.ml=\max(tr_{ls}.ml,tr_{ls}.sum+tr_{rs}.ml)\)
\(tr_p.mr=\max(tr_{rs}.mr,tr_{rs}.sum+tr_{ls}.ml)\)
这个自行对照画图
\(tr_p.ans=\max(\max(tr_{ls}.ans,tr_{rs}.ans),tr_{ls}.mr+tr_{rs}.ml)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int n, m;
struct node
{
int l, r;
ll maxleft, maxright, sum, ans;
} tr[N];
void pushon(int p)
{
tr[p].sum = tr[p * 2].sum + tr[p * 2 + 1].sum;
tr[p].maxleft = max(tr[p * 2].maxleft, tr[p * 2].sum + tr[p * 2 + 1].maxleft);
tr[p].maxright = max(tr[p * 2 + 1].maxright, tr[p * 2 + 1].sum + tr[p * 2].maxright);
tr[p].ans = max(max(tr[p * 2].ans, tr[p * 2 + 1].ans), tr[p * 2].maxright + tr[p * 2 + 1].maxleft);
}
void build(int p, int l, int r)
{
tr[p].l = l, tr[p].r = r;
if (l == r)
{
cin >> tr[p].sum;
tr[p].maxleft = tr[p].maxright = tr[p].ans = tr[p].sum;
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
pushon(p);
}
node ask(int p, int ql, int qr)
{
if (ql <= tr[p].l && tr[p].r <= qr)
return tr[p];
int mid = (tr[p].l + tr[p].r) >> 1;
if (qr <= mid)
return ask(p * 2, ql, qr);
else
{
if (ql > mid)
return ask(p * 2 + 1, ql, qr);
node t, a = ask(p * 2, ql, qr), b = ask(p * 2 + 1, ql, qr);
t.maxleft = max(a.maxleft, a.sum + b.maxleft);
t.maxright = max(b.maxright, a.maxright + b.sum);
t.ans = max(max(a.ans, b.ans), a.maxright + b.maxleft);
return t;
}
}
void update(int p, int a, int x)
{
if (tr[p].l == tr[p].r)
{
tr[p].maxleft = tr[p].maxright = tr[p].ans = tr[p].sum = x;
return;
}
int mid = (tr[p].l + tr[p].r) >> 1;
if (a <= mid)
update(p * 2, a, x);
else
update(p * 2 + 1, a, x);
pushon(p);
}
int main()
{
cin >> n >> m;
build(1, 1, n);
while (m--)
{
int opt, x, y;
cin >> opt >> x >> y;
if (opt == 1)
{
if (x > y)
swap(x, y);
cout << ask(1, x, y).ans << endl;
}
else
update(1, x, y);
}
return 0;
}