# 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!
{"ft_lang_label":"__label__en","ft_lang_prob":0.79437083,"math_prob":0.9987804,"size":1532,"snap":"2023-40-2023-50","text_gpt3_token_len":393,"char_repetition_ratio":0.125,"word_repetition_ratio":0.04109589,"special_character_ratio":0.26762402,"punctuation_ratio":0.13855422,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999697,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-23T01:53:03Z\",\"WARC-Record-ID\":\"<urn:uuid:7e3bdeea-249a-4b47-a94b-e2cebbe71b68>\",\"Content-Length\":\"379447\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fa89d31d-9f5b-4e24-9be2-c05323e6937b>\",\"WARC-Concurrent-To\":\"<urn:uuid:42545a18-1e20-45a3-9c02-a4eb61cdc59d>\",\"WARC-IP-Address\":\"76.76.21.21\",\"WARC-Target-URI\":\"https://usaco.guide/problems/cses-2166-prefix-sum-queries/solution\",\"WARC-Payload-Digest\":\"sha1:WFZRRAOLDHIP6LIHC4BRH5RYEQ4HMRBD\",\"WARC-Block-Digest\":\"sha1:Z4BJD4GGNJLI2GUSM3CXDH5QTVYQWVCH\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233506429.78_warc_CC-MAIN-20230922234442-20230923024442-00659.warc.gz\"}"}