Checksum Window Queries

MediumBit Manipulation

Problem

A firmware image is split into blocks with checksums blocks. Engineers repeatedly ask for the XOR checksum of a window of consecutive blocks.

For each query [left, right] in queries, return blocks[left] XOR blocks[left + 1] XOR … XOR blocks[right]. Return the answers in query order.

Example 1

Input:
blocks = [3, 8, 2, 6], queries = [[0, 1], [1, 3], [2, 2], [0, 3]]
Output:
[11, 12, 2, 15]

3^8 = 11, 8^2^6 = 12, 2, 3^8^2^6 = 15.

Example 2

Input:
blocks = [5, 5, 5], queries = [[0, 2], [0, 1], [1, 1]]
Output:
[5, 0, 5]

Constraints

  • 1 ≤ blocks.length ≤ 3 · 10^4
  • 0 ≤ blocks[i] < 2^31
  • 1 ≤ queries.length ≤ 3 · 10^4
  • 0 ≤ left ≤ right < blocks.length

Hint

Show the first hint

Recomputing every window from scratch costs up to n per query. Is there a prefix structure for XOR, like prefix sums for addition?

Walkthrough

How to approach it

01Clarify before coding

  • Are the bounds inclusive? Yes, both left and right.
  • Can a query cover a single block? Yes, left = right.
  • Is the data static between queries? Yes, so precomputation pays off.

02Brute force

For each query, XOR the blocks from left to right.

Cost: O(n · q) time: 9 · 10^8 operations at the limits, too slow.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.