CSES - Prefix Sum Queries

Time Complexity: $\mathcal O(N\log N)$

In this problem, we're given an array $a$ and we're asked to answer 2 types of queries

1. update the value at position $i$ to $x$
2. calculate the maximum prefix sum in the range $[a, b]$

Solution 1 - Segment Tree

In each segment tree node, we will store

• $\texttt{sum}$: the sum of the elements in the range
• $\texttt{pref}$: the maximum prefix sum in the range

To calculate $\texttt{seg}[i]$,

• The $\texttt{sum}$ would be equal to $\texttt{left}.\texttt{sum} + \texttt{right}.\texttt{sum}$.
• The maximum prefix has to end at either the left segment ($\texttt{left}.\texttt{pref}$), or at the right segment ($\texttt{left}.\texttt{sum} + \texttt{right}.\texttt{pref}$), so $\texttt{pref}$ would equal $\max(\texttt{left}.\texttt{pref}, \texttt{left}.\texttt{sum} + \texttt{right}.\texttt{pref})$.

Now we can build and update any value in our segment tree.

To answer an query, we can split the range $[l, r]$ into $\mathcal O(\log N)$ segments. To calculate the answer, we just repeatedly merge these segments until there is one left and take the $\texttt{pref}$.

Copy
#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;

Solution 2 - With Lazy Propagation

We can use a segment tree with lazy propagation to solve this problem. Let $\texttt{ps}[i]$ be the sum of $a_1, a_2, \dots a_i$. We can maintain a segment tree consisting of the maximum $\texttt{ps}$ in the range of $[l,r]$.

To update the value at position $i$ to $x$, we add $x-a_i$ to each of the values in the range $[i,N]$.

To answer a query of type 2, our answer would be $\max_{i \in [a, b]}(\texttt{ps}[i]) - \texttt{ps}[{a-1}]$.

Copy
#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); }