Максимальная сумма подотрезка на заданном отрезке
Дан массив .
Необходимо обработать запросов двух типов:
1 i x — присвоить 2 l r — найти максимальную сумму подмассива внутри отрезка Подмассив должен быть непустым.
struct Node?Чтобы эффективно объединять два отрезка, в каждом узле дерева отрезков будем хранить:
sum — сумма всего отрезкаpref — максимальная сумма префиксаsuf — максимальная сумма суффиксаres — максимальная сумма подотрезка внутриТакой подход позволяет реализовать объединение через одну функцию comb(L, R).
Пусть есть два узла:
LRТогда:
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)В функции get(...) при tl > tr возвращается Node().
Нужно, чтобы:
Поэтому удобно сделать:
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() {
// пустой узел (нейтральный элемент для запроса)
sum = 0;
pref = suf = res = NEG_INF;
}
Node(long long x) {
// лист (отрезок из одного элемента)
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;
}