Range Sum Queries and the Off-by-One That Kills Candidates

Concepts: pyRangeSumQuery, pyOffByOne

The range sum formula is: sum(i, j) = prefix[j+1] - prefix[i]. This gives you the sum of arr[i], arr[i+1], ..., arr[j] inclusive. If you internalize the 1-indexed prefix convention (prefix[0] = 0, prefix[k] = sum of first k elements), this formula is the only one you need. But there is an off-by-one trap that catches a shocking percentage of candidates -- even experienced ones. The +1 on j is the most common omission. Let me show you exactly why it is there. The Formula Derivation (so you never forget it) prefix[j+1] = sum of arr[0..j] (all elements from 0 to j inclusive). prefix[i] = sum of arr[0..i-1] (all elements from 0 to i-1 inclusive). Subtracting: prefix[j+1] - prefix[i] = sum of arr[i..j]. The sentinel prefix[0] = 0 makes this work for i=0 with no special case: prefix[j+1] - prefi