Blocks: add and largest

Use square-root decomposition (lesson 6) for two operations on a list: add(l, r, v) adds v to every value of a[l:r], and largest(l, r) returns the largest value of a[l:r].

b = Blocks([5, 2, 7, 4, 6, 1, 8, 3])
b.largest(0, 8)     # 8
b.add(1, 7, 3)      # [5, 5, 10, 7, 9, 4, 11, 3]
b.largest(3, 6)     # 9

Every range is half-open, as in Python slices: (l, r) means positions l up to but not including r, the same values as a[l:r].

Ranges for largest are never empty; an empty range for add changes nothing. A lazy segment tree also solves this, and passes the tests.

Limits

• Up to 160,000 values and 2,000 operations over wide ranges. Each operation should cost about O(√n); looping over the whole range is too slow.