A packet is a list of byte values data. The checksum of a segment is the bitwise XOR of all bytes in it. For each query [l, r] return the checksum of data[l..r] inclusive.
Examples
Input: data = [6, 3, 5, 1], queries = [[0, 1], [1, 3], [2, 2]]
Output: [5, 7, 5]
Explanation: 6 ^ 3 = 5; 3 ^ 5 ^ 1 = 7; a single byte is its own checksum.
Input: data = [9], queries = [[0, 0]]
Output: [9]
Constraints
- Every query
[l, r]hasl <= r. - Target complexity: O(n + q). XOR-ing each segment from scratch is too slow for the largest tests.
Goals
- See that XOR has an inverse just like addition does
- Answer XOR range queries in O(1) with a prefix array