Range add, point query

easy ~15 min

You get an array of n integers and a list of queries, processed in order. Positions are 1-indexed.

(1, a, b, u): add u to every value at positions a..b inclusive.
(2, k): report the current value at position k.

Write range_update_queries(nums, queries) -> list[int] returning the answers to the type-2 queries, in order.

range_update_queries([3, 2, 4, 5], [(1, 2, 3, 10), (2, 3), (1, 1, 4, -1), (2, 1), (2, 3)])
# [14, 2, 13]

Constraints: 1 <= n <= 2·10^5, up to 2·10^5 queries; values and u up to 10**9 in absolute value, so values can exceed 32 bits. Looping over a..b per update is O(n); aim for O(log n) per query.

Show hint

Instead of the values, track how much each value differs from the one before it. A range add then changes only two of those differences, and a single value is a prefix sum of them, which a suitable structure maintains in O(log n).

Topic: Segment tree (+ lazy propagation). Any associative range query with point or range updates in O(log n).

Read the visual guide