Prefix Sums
Precompute running totals once so any range sum, range XOR or range update is answered in constant time.
The problem
You get an array of n numbers and q questions. Each question gives two positions l and r and asks for the sum of the elements between them. With n and q both up to 200,000, how do you answer fast?
1 of 11