Indian Computing Olympiad

Range queries

Range queries with single point updates

Suppose we want to report sum(A[i]..A[j]) rather than min(A[i]..A[j]). We can compute the prefix sums

P[i] = sum(A[1]..A[i])

for each i, and report

sum(A[i],A[j]) = P[j] - P[i]

Suppose we additionally allow the array to be updated. We get a sequence of instructions of the form

• Update(i,a) : update A[i] to A[i] + a

• Sum(i,j) : report the sum from A[i] to A[j]

If we do this naively, we can update the values in constant time, but we have to actually count the sum from A[i] to A[j]—we cannot precompute prefix sums because the values are changing.

We need a new data structure. Two useful data structures are:

• Binary index trees
• Segment trees