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})$$$
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!