Maximum subarray sum on a given segment
An array is given.
It is necessary to process queries of two types:
1 i x — assign 2 l r — find the maximum subarray sum inside the segment The subarray must be non-empty.
struct Node?To efficiently merge two segments, in each node of the segment tree we will store:
sum — the sum of the whole segmentpref — the maximum prefix sumsuf — the maximum suffix sumres — the maximum subsegment sum insideThis approach allows implementing merging via a single function comb(L, R).
Suppose there are two nodes:
LRThen:
sum = L.sum + R.sumpref = max(L.pref, L.sum + R.pref)suf = max(R.suf, R.sum + L.suf)res = max(L.res, R.res, L.suf + R.pref)In the function get(...), when tl > tr it returns Node().
It is necessary that:
Therefore it is convenient to do:
sum = 0pref = suf = res = -INFstruct Node {
long long res;
long long pref;
long long suf;
long long sum;
Node() {
// empty node
// todo: implement your logic
}
Node(long long x) {
// node with value of x, you can change arguments
// todo: implement your logic
}
};
Node comb(const Node &L, const Node &R) {
Node cur;
// todo: implement your logic
return cur;
}
int n;
int a[N];
Node t[4 * N];
void build(int x, int l, int r) {
if (l == r) {
t[x] = Node(a[l]);
return;
}
int m = (l + r) / 2;
build(x * 2, l, m);
build(x * 2 + 1, m + 1, r);
t[x] = comb(t[x * 2], t[x * 2 + 1]);
}
void upd(int x, int l, int r, int i, int y) {
if (l == r) {
t[x] = Node(y);
return;
}
int m = (l + r) / 2;
if (i <= m) {
upd(x * 2, l, m, i, y);
} else {
upd(x * 2 + 1, m + 1, r, i, y);
}
t[x] = comb(t[x * 2], t[x * 2 + 1]);
}
Node get(int x, int l, int r, int tl, int tr) {
if (tl > tr) {
return Node();
} else if (l == tl && r == tr) {
return t[x];
}
int m = (l + r) / 2;
return comb(get(x * 2, l, m, tl, min(m, tr)),
get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr));
}
const long long NEG_INF = -(1LL << 60);
struct Node {
long long res;
long long pref;
long long suf;
long long sum;
Node() {
// empty node (neutral element for the query)
sum = 0;
pref = suf = res = NEG_INF;
}
Node(long long x) {
// leaf (segment of one element)
sum = x;
pref = suf = res = x;
}
};
Node comb(const Node &L, const Node &R) {
Node cur;
cur.sum = L.sum + R.sum;
cur.pref = max(L.pref, L.sum + R.pref);
cur.suf = max(R.suf, R.sum + L.suf);
cur.res = max({L.res, R.res, L.suf + R.pref});
return cur;
}