Learning pathOriginal reference
Lesson 5 of 8

Answer range XOR queries

Reuse prefix cancellation and the four-case XOR pattern for consecutive integers.

Understand the idea

Set prefix[0] = 0 and prefix[i + 1] = prefix[i] XOR a[i]. The XOR of a half-open interval [l, r) is prefix[r] XOR prefix[l]: all earlier elements appear twice and cancel. Unlike sum subtraction, the inverse operation here is XOR itself.

Trace a small example

For [5, 2, 7], prefixes are [0, 5, 7, 0]. The XOR over positions [1, 3) is 0 XOR 5 = 5, matching 2 XOR 7. XOR from 0 through n follows n, 1, n + 1, 0 for n modulo 4 equal to 0, 1, 2, 3.

Conditions and cost

Build prefixes in O(n), then answer each query in O(1). For inclusive [L, R] of nonnegative integers, use F(R) XOR F(L − 1), with a separate L = 0 case to avoid unsigned underflow.

Prefix sum explorer

Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.

Input array a

30
11
42
13
54
95

Prefix array P

00
31
42
83
94
145
236
P[5] − P[1] = 14 − (3) = 11

Preprocess once in O(n). Each range sum then takes O(1).

Guided simulation · Change the inputs to test your understanding.

Pause & predict

Which expression gives XOR of a[l..r) from a prefix XOR array?

Choose an answer
Try it yourself

Turn the idea into code

Compute XOR of all integers from 4 through 7.

Give me a hint

Use the four-case pattern or cancel by hand.

Show the explained solution

F(7) = 0 and F(3) = 0, so the range XOR is 0. Directly, 4 XOR 5 = 1 and 6 XOR 7 = 1.

Your notes

Ready for the next idea?

Mark complete when you can explain it yourself.

From a problem to a programIdentify the input, output, and constraints, then translate a small plan into C++.Variables, types, and remembered valuesChoose a representation, initialize it, and understand what assignment really changes.Arithmetic without surprisesPredict division and remainder, widen before multiplication, and format decimal answers.Conditions and logical decisionsBuild exclusive categories, combine comparisons, and protect operations with short-circuit logic.Optional: other ways to chooseRecognize switch for exact choices and the conditional operator for choosing a value.For loops: make repetition preciseTrace initialization, condition, body, and update—and avoid an extra iteration.While, do-while, and stopping rulesChoose a loop from its stopping condition and read the exact input format.Break, continue, and early answersDistinguish leaving a loop from skipping one iteration, without losing required input.Five patterns worth understandingUse sums, counts, best-so-far candidates, products, and flags to process a stream.Nested loops: rows and columnsTranslate a shape into two loop roles and count the total work.Take a number apart, one digit at a timeUse remainder and division to process decimal digits, including zero.Multiple cases and a debugging mindsetCombine the patterns, isolate each case, and test the boundaries that can break your idea.Arrays: give every value a placeUnderstand indices, initialization, capacity, active length, and the first safe array loop.Scan, count, search, and compareDistinguish values from positions and preserve the exact tie rule a problem asks for.Change a sequence without losing itUpdate, copy, compare, reverse, and inspect neighbours using the correct bounds.Matrices: think in two coordinatesTraverse tables, total rows and columns, inspect diagonals, and protect grid neighbours.Characters become stringsSeparate characters from numbers, then safely inspect and edit managed text.Read the text the problem actually givesChoose words or full lines, preserve empty cases, and reset only the state that needs it.Scan text: count, filter, transformBuild a result from matching characters without losing leading zeros or skipping shifted text.Join, compare, and find textLearn content comparison, lexicographical order, substring counts, and the not-found sentinel.