# CSES - Prefix Sum Queries

Author: Dong Liu

### Appears In

Solution 1 - Segment TreeSolution 2 - With Lazy Propagation

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

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!