Segment Tree (Range Sum Query) - Classic Problems | Repovive

CLS28. Segment Tree (Range Sum Query)

2s256 MB

Given an array of $n$ integers, process $q$ queries:

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ t_1 \quad a_1 \\ t_2 \quad a_2 \\ \vdots \\ t_q \quad a_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_k \end{array}

k = \#\{\text{type } 2 \text{ queries}\}

Input

Explanation

For this input, the required output is 6 14.

Output

6
14

Input

Explanation

For this input, the required output is 4 2.

Output

4
2

Input

Explanation

For this input, the required output is 4 14 7.

Output

4
14
7

Given an array of $n$ integers, process $q$ queries:

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ t_1 \quad a_1 \\ t_2 \quad a_2 \\ \vdots \\ t_q \quad a_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_k \end{array}

k = \#\{\text{type } 2 \text{ queries}\}