我们可以分析出上题就是带修改的最大子段和[-](http://jvquant.com/wiki/行情/解析行情.html)
遇到这种类型的题目应该想到用线段树[-](http://jvquant.com/wiki/行情/订阅/美股行情订阅.html)
实现
对于原数列，先建起一棵线段树，每个节点包含 最大前缀、最大后缀、最大字段和、区间和 信息[-]()
当你明确一道题是线段树时，要先思考 pushup 和 pushdown 怎么写，因为剩下的都是差不多的[-](http://jvquant.com/wiki/行情/发送订阅指令.html) —— jzp.
因为本题是单查，没有 pushdown，就先考虑 pushup 怎么写：
最大前缀只可能是左儿子的最大前缀或是左儿子的和加上右儿子的最大前缀，即
[-](http://jvquant.com/wiki/行情/解析/沪深行情解析.html)
最大后缀同理，
[-]()
最大子段和就是左儿子最大子段和或右儿子最大子段和或左儿子最大后缀加右儿子最大前缀，即
[-](http://jvquant.com/wiki/数据库/可转债基本信息查询.html)
区间和很简单，不赘述[-](http://jvquant.com/wiki/券商交易接口/撤销委托.html)
void pushup(int id) {
sum(id) = sum(ls) + sum(rs);
maxl(id) = max(maxl(ls), sum(ls) + maxl(rs));
maxr(id) = max(maxr(rs), sum(rs) + maxr(ls));
maxs(id) = max(max(maxs(ls), maxs(rs)), maxr(ls) + maxl(rs));
}
那么对于每一次询问，我们找到线段树上的左右端点
、
对应的两点
、
[-](http://jvquant.com/wiki/行情/连接WebSocket.html)
当我们从上往下爬树爬到
时，
和
就会分开为两个区间[-](http://jvquant.com/wiki/行情/解析/港股行情解析.html)
此时答案有几种可能：
，其中
为该区间的中间点，此时递归左侧得到答案[-](http://jvquant.com/wiki/行情/SDK/PHP接入WebSocket行情.html)
，此时递归右侧得到答案[-](http://jvquant.com/wiki/帮助/价格/委托交易.html)
，此时合并两次得到的答案[-](http://jvquant.com/wiki/开始使用/分配服务器.html)
以上三者取最大值返回[-](http://jvquant.com/wiki/帮助/价格/数据库服务.html)
这跟 cdq 分治的思想有异曲同工之妙[-](http://jvquant.com/wiki/数据库/沪深分时数据.html)
当
与
并没有分叉时，就直接走下去即可[-](http://jvquant.com/wiki/行情/数据库行情.html)
那么此时查询也可以顺利地写出来了[-](http://jvquant.com/wiki/数据库/沪深K线查询.html)
segment query(int id, int lft, int rht, int l, int r) { // 这里用 segment 作为返回值是因为每层递归都需要用到下一层递归的结果
if (l <= lft && rht <= r) return seg[id];
int mid = (lft + rht) >> 1;
if (r <= mid) return query(ls, lft, mid, l, r);
if (l > mid) return query(rs, mid + 1, rht, l, r);
segment a = query(ls, lft, mid, l, r), b = query(rs, mid + 1, rht, l, r), t;
t.sum = a.sum + b.sum;
t.maxl = max(a.maxl, a.sum + b.maxl);
t.maxr = max(b.maxr, b.sum + a.maxr);
t.maxs = max(max(a.maxs, b.maxs), a.maxr + b.maxl);
return t;
}
整体代码：
struct segment_tree {
#define ls (id << 1)
#define rs (id << 1 | 1)
#define sum(id) seg[id].sum
#define maxl(id) seg[id].maxl
#define maxr(id) seg[id].maxr
#define maxs(id) seg[id].maxs
struct segment {
int maxl, maxr;
int sum, maxs;
} seg[N << 2];
void pushup(int id) {
sum(id) = sum(ls) + sum(rs);
maxl(id) = max(maxl(ls), sum(ls) + maxl(rs));
maxr(id) = max(maxr(rs), sum(rs) + maxr(ls));
maxs(id) = max(max(maxs(ls), maxs(rs)), maxr(ls) + maxl(rs));
}
void build(int id, int lft, int rht) {
if (lft == rht) {
sum(id) = a[lft];
maxl(id) = maxr(id) = maxs(id) = a[lft];
return;
}
int mid = (lft + rht) >> 1;
build(ls, lft, mid), build(rs, mid + 1, rht);
pushup(id);
}
void change(int id, int lft, int rht, int x, int v) {
// if (lft > x || rht < x) return;
if (lft == rht) {
// a[lft] = v;
sum(id) = v;
maxl(id) = maxr(id) = maxs(id) = v;
return;
}
int mid = (lft + rht) >> 1;
if (x <= mid) change(ls, lft, mid, x, v);
else change(rs, mid + 1, rht, x, v);
pushup(id);
}
segment query(int id, int lft, int rht, int l, int r) {
// if (lft > r || rht < l) return ;
if (l <= lft && rht <= r) return seg[id];
int mid = (lft + rht) >> 1;
if (r <= mid) return query(ls, lft, mid, l, r);
if (l > mid) return query(rs, mid + 1, rht, l, r);
segment a = query(ls, lft, mid, l, r), b = query(rs, mid + 1, rht, l, r), t;
t.sum = a.sum + b.sum;
t.maxl = max(a.maxl, a.sum + b.maxl);
t.maxr = max(b.maxr, b.sum + a.maxr);
t.maxs = max(max(a.maxs, b.maxs), a.maxr + b.maxl);
return t;
}
} seg;
我们可以通过线段树维护最大子段和来推广到其他类似的问题[-](http://jvquant.com/wiki/行情/SDK/Java接入WebSocket行情.html)
[-](http://jvquant.com/wiki/券商交易接口/券商交易接口调用.html)
