### Qualified's blog

By Qualified, history, 7 weeks ago, You are given a number $n$ and a number $m$ and an array $a$ of $n$ numbers and 2 types of queries. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $l, r, x$. You add all the numbers from $l$ to $r$(inclusive) by $x$. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}

2) Given 1 number $y$, output $a[y]$. This should be self explanatory.

At the end print the array $a$.

$m$ describes the number of queries being asked.

Example:

4 3
1 9 2 2
2 2 3
0 3 5
2


Output:

10
6 14 10 7


Should be less that $O(n^{2})$ Comments (6)
 » Segment tree?
•  » » Isn't SegTree for finding the sum of numbers in a range? Am I stupid?
•  » » » Yes, SegTrees are for that. For the first query just use Lazy Propagation, for the second your range is l = r = y.
•  » » » » Amazingly enough, you don't even need lazy propagation. You can just swap the logic in the update and query function. Update adds a value to a set of nodes, and query accumulates values as it moves down from the root to the leaf.
•  » » » » » WOW! Thanks for sharing that!
•  » » » Consider a segment tree on the "change in value" so we can use the so called "+1/-1 trick" and if we want to increment [L, R] by X, we can increment L by X and R+1 by -X