# CSES - Prefix Sum Queries

Author: Dong Liu

**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

- update the value at position $i$ to $x$
- 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}$.

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;

## 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}]$.

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

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!