Why can't a sparse table answer range sums?

A strong answer

The sparse table's O(1) query reads at most two precomputed blocks that cover the range, and those blocks are allowed to overlap. That is only correct when repeating an element changes nothing, which is idempotence: min, max and gcd all ignore duplicates, so the minimum of two overlapping blocks is the minimum of their union. Sum is associative but not idempotent, and an overlap adds the shared elements twice. For a range of nine elements, the query takes two blocks of eight, and the seven elements in the overlap are counted twice: with 3, 1, 4, 1, 5, 9, 2, 6, 1, the true sum through position nine is 32, while the two blocks add to 60, which is 32 plus the 28 elements in the overlap counted again.

The obvious repair fails. Two aligned power-of-two blocks cannot tile an arbitrary range: for a seven-element range the left block of four and the right block of two leave position five uncovered, and for longer ranges the blocks overlap instead. The segment tree solves this by taking O(log n) disjoint nodes, and the sparse table's entire claim was a query of exactly two lookups.

For sums specifically, there is a simpler point: a static range sum needs no table at all. Prefix sums answer every range sum with two subtractions, O(1) time and O(n) space, so the sparse table exists for the operations where prefix tricks do not work. When sums must also be updated, the answer is the structure built for it, a Fenwick tree or segment tree at O(log n) per update and query, or sqrt decomposition with block sums for cheaper updates and an O(sqrt n) query. There is a specialist structure, the disjoint sparse table, that answers any associative operation with two disjoint blocks in O(1), at O(n log n) space and a static array; it is worth naming if you know it, and worth noting that the memory buys you nothing over prefix sums for plain sums.

What the interviewer is listening for

• Idempotence, not commutativity, as the property the two-block query depends on.
• The overlap double-counts for sum, and the aligned blocks cannot be made disjoint with two of them.
• Static range sums are already solved by prefix sums, so the sparse table adds nothing there.
• Updates change the answer again: Fenwick or segment tree at O(log n), sqrt decomposition as the middle option.

Common mistakes

• Saying sums are unsupported because sums are not commutative, when order never mattered and the real issue is duplicate elements.
• Taking k as the floor of the log of the range length and assuming the two blocks sit side by side.
• Proposing to subtract the overlap, which needs a third block or a nested structure and no longer costs two lookups.
• Forgetting prefix sums, so the answer defends the sparse table instead of noticing that sums are the easy static case.