Prefix Sum Queries

Complejidad temporal: $\mathcal O(N\log N)$

En este problema, se nos da un arreglo $a$ y se nos pide responder 2 tipos de consultas

actualizar el valor en la posición $i$ a $x$
calcular la suma de prefijos máxima en el rango $[a, b]$

Solución 1 - Árbol de Segmentos

En cada nodo del árbol de segmentos, guardaremos

$\texttt{sum}$ : la suma de los elementos en el rango
$\texttt{pref}$ : la suma de prefijos máxima en el rango

Para calcular $\texttt{seg}[i]$ ,

El $\texttt{sum}$ sería igual a $\texttt{left}.\texttt{sum} + \texttt{right}.\texttt{sum}$ .
El prefijo máximo tiene que terminar o bien en el segmento izquierdo ( $\texttt{left}.\texttt{pref}$ ), o bien en el segmento derecho ( $\texttt{left}.\texttt{sum} + \texttt{right}.\texttt{pref}$ ), así que $\texttt{pref}$ sería igual a $\max(\texttt{left}.\texttt{pref}, \texttt{left}.\texttt{sum} + \texttt{right}.\texttt{pref})$ .

Ahora podemos construir y actualizar cualquier valor en nuestro árbol de segmentos.

Para responder una consulta, podemos partir el rango $[l, r]$ en $\mathcal O(\log N)$ segmentos. Para calcular la respuesta, simplemente fusionamos estos segmentos de forma repetida hasta que quede uno y tomamos el $\texttt{pref}$ .

C++


#include <bits/stdc++.h>
using namespace std;
 
const int N = 200010;
const int S = 1 << 18;
 
int n, q, a[N];
 
struct node {
	long long sum, pref;
	node(long long sum, long long pref) : sum(sum), pref(pref) {}
	node(long long x = 0) : sum(x), pref(max(0LL, x)) {}
	friend node operator+(const node &a, const node &b) {
		return {a.sum + b.sum, max(a.pref, a.sum + b.pref)};
	}
} tt[S << 1];
 
void build(int k = 1, int l = 1, int r = n) {
	if (l == r) {
		tt[k] = node(a[l]);
		return;
	}
	int m = (l + r) >> 1;
	build(k << 1, l, m);
	build(k << 1 | 1, m + 1, r);
	tt[k] = tt[k << 1] + tt[k << 1 | 1];
}
 
void update(int i, int x, int k = 1, int l = 1, int r = n) {
	if (l == r) {
		tt[k] = node(x);
		return;
	}
	int m = (l + r) >> 1;
	if (i <= m) update(i, x, k << 1, l, m);
	else update(i, x, k << 1 | 1, m + 1, r);
	tt[k] = tt[k << 1] + tt[k << 1 | 1];
}
 
node query(int ql, int qr, int k = 1, int l = 1, int r = n) {
	if (ql > r || qr < l) return 0;
	if (ql <= l && qr >= r) return tt[k];
	int m = (l + r) >> 1;
	node q1 = query(ql, qr, k << 1, l, m);
	node q2 = query(ql, qr, k << 1 | 1, m + 1, r);
	return q1 + q2;
}
 
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	build();
	for (int i = 0, t, x, y; i < q; ++i) {
		scanf("%d%d%d", &t, &x, &y);
		if (t == 1) update(x, a[x] = y);
		else printf("%lld\n", query(x, y).pref);
	}
}

Solución 2 - Con propagación perezosa

Podemos usar un árbol de segmentos con propagación perezosa para resolver este problema. Sea $\texttt{ps}[i]$ la suma de $a_1, a_2, \dots a_i$ . Podemos mantener un árbol de segmentos que consiste en el $\texttt{ps}$ máximo en el rango $[l,r]$ .

Para actualizar el valor en la posición $i$ a $x$ , sumamos $x-a_i$ a cada uno de los valores en el rango $[i,N]$ .

Para responder una consulta de tipo 2, nuestra respuesta sería $\max_{i \in [a, b]}(\texttt{ps}[i]) - \texttt{ps}[{a-1}]$ .

C++


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
template <class T> struct LSegTree {
	int N;
	vector<T> t, lz;
	T U = -1e18;
	T F(T i, T j) { return max(i, j); }
	LSegTree() {}
	LSegTree(int N) : N(N), t(4 * (N + 1), U), lz(4 * (N + 1), 0) {}
	void pull(int i) { t[i] = F(t[i * 2], t[i * 2 + 1]); }
	void push(int i, int l, int r) {
		t[i] += lz[i];
		if (l != r) lz[i * 2] += lz[i], lz[i * 2 + 1] += lz[i];
		lz[i] = 0;
	}
	void build(vector<ll> &v) { build(v, 1, 0, N); }
	void build(vector<ll> &v, int i, int l, int r) {
		if (l == r) {
			t[i] = v[l];
			return;
		}
		int m = (l + r) / 2;
		build(v, i * 2, l, m);
		build(v, i * 2 + 1, m + 1, r);
		pull(i);
	}
	void upd(int L, int R, T v) { upd(L, R, v, 1, 0, N); }
	void upd(int L, int R, T v, int i, int l, int r) {
		push(i, l, r);
		if (R < l || L > r) return;
		if (L <= l && R >= r) {
			lz[i] += v;
			push(i, l, r);
			return;
		}
		int m = (l + r) / 2;
		upd(L, R, v, i * 2, l, m);
		upd(L, R, v, i * 2 + 1, m + 1, r);
		pull(i);
	}
	T qry(int L, int R) { return qry(L, R, 1, 0, N); }
	T qry(int L, int R, int i, int l, int r) {
		push(i, l, r);
		if (R < l || L > r) return U;
		if (L <= l && R >= r) return t[i];
		int m = (l + r) / 2;
		return F(qry(L, R, i * 2, l, m), qry(L, R, i * 2 + 1, m + 1, r));
	}
};
 
int n, q;
vector<ll> a, ps;
LSegTree<ll> st;
 
int main() {
 
	cin >> n >> q;
	a = ps = vector<ll>(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
 
	// construct ps
	ps[0] = 0;
	for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];
 
	// construct the segment tree
	st = LSegTree<ll>(n);
	st.build(ps);
 
	// queries
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			// update a[i] to x
			int i;
			ll x;
			cin >> i >> x;
			st.upd(i, n, x - a[i]);
			a[i] = x;
		} else {
			// max ps in the range [a,b] - ps[a-1]
			int a, b;
			cin >> a >> b;
			cout << st.qry(a - 1, b) - st.qry(a - 1, a - 1) << '\n';
		}
	}
}