CSES - Range Update Queries

Explanation

We can solve this problem by taking advantage of a difference array, where $\texttt{diff}[i] = \texttt{arr}[i]-\texttt{arr}[i-1]$ for all $i$ $(1 \leq i \leq n)$. To calculate $\texttt{arr}[i]$ using $\texttt{diff}$, we can find the sum of all the values in $\texttt{diff}$ up to the $i$-th index:

This means that we can answer point queries in $\mathcal{O}(\log n)$ time by calculating prefix sums of $\texttt{diff}$ with a segment tree or binary-indexed tree.

To respond to range updates on an interval $[a, b]$, we can increment $\texttt{diff}[a]$ by $u$ and decrement $\texttt{diff}[b+1]$ by $u$. This way, when answering point queries, all the values at indices $a \dots b$ will be increased by $u$ and all values at indices less than $a$ or greater than $b$ remain unchanged.

Implementation

Time Complexity: $\mathcal{O}(q\log n)$

Copy
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

template <class T> struct Seg {
	int n;
	T ID = 0;
	vector<T> seg;

Copy
import java.io.*;
import java.util.*;

public class RangeUpdateQueries {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int q = io.nextInt();

		int[] arr = new int[n + 1];