071 — Prefix XOR¶

মজার ব্যাপার দেখো: 067-এর prefix sum-এর পুরো template-টা প্রায় হুবহু চলে, শুধু + সরিয়ে ^ (XOR) বসালে। কেন? কারণ Level 4-এ শেখা XOR-এর সেই জাদু — a ^ a = 0 — বিয়োগের কাজটা নিজেই করে দেয়। এই note-এ আমরা দেখব একই কৌশল কীভাবে অন্য operator-এ ফিরে আসে। ধীরে পড়ো, cancel-এর ছবিটা মনে রাখো।

Source¶

Original source: Classic technique (prefix XOR for range XOR queries)
Platform: CSES Range Xor Queries — https://cses.fi/problemset/task/1650
Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
Difficulty: Medium
Pattern: prefix XOR (range XOR via PX[r+1] ^ PX[l])
Basic idea inherited from: 067 — Prefix Sum (এবং Level 4-এর 060 — XOR basics)

1. Problem in simple words¶

একটা সংখ্যার array a আর অনেকগুলো query দেওয়া। প্রতিটা query-তে দুটো index l আর r — তোমাকে বলতে হবে a[l] ^ a[l+1] ^ ... ^ a[r] কত (এখানে ^ হলো bitwise XOR, দুই প্রান্ত সহ)।

ঠিক range sum (068)-এর মতোই, শুধু যোগের জায়গায় XOR। query অনেক হলে প্রতিবার loop চালালে ধীর। তাই আগে একটা prefix XOR array বানিয়ে নিয়ে, তারপর প্রতিটা query O(1)-এ দিতে হবে।

2. What is the math idea?¶

মূল idea হলো prefix XOR আর XOR-এর self-inverse ধর্ম।

XOR-এর দুটো মূল ধর্ম মনে করো (Level 4):

x ^ x = 0 (একই জিনিস দুবার XOR করলে কেটে যায় — self-inverse)
x ^ 0 = x (0-এর সাথে XOR করলে বদলায় না)

তাই prefix XOR বানাই: PX[i+1] = PX[i] ^ a[i]। আর range XOR:

xor(l..r) = PX[r+1] ^ PX[l]

কারণ PX[r+1]-এ আছে a[0]^...^a[r], আর PX[l]-এ আছে a[0]^...^a[l-1]। দুটো XOR করলে বাঁ দিকের অংশ (a[0]..a[l-1]) দুবার এসে কেটে যায় — পড়ে থাকে শুধু a[l]^...^a[r]। বিয়োগ যা subtraction-এ করত, XOR তা cancellation-এ করছে।

3. Which basic idea does this inherit from?¶

দুটো জায়গা থেকে: 067 (Prefix Sum)-এর template, আর Level 4-এর 060 (XOR basics)-এর self-inverse ধর্ম।

067-এ ছিল P[i+1] = P[i] + a[i] আর sum = P[r+1] - P[l]। এখানে + → ^, আর - → ^ (কারণ XOR-এর undo XOR নিজেই)। মূল কাঠামো এক, operator বদল।

বড় শিক্ষাটা এই: prefix কৌশল চলে যেকোনো operation-এ যার "undo" আছে। যোগের undo বিয়োগ, XOR-এর undo XOR। তাই দুটোতেই prefix কাজ করে। (Min/max-এর undo নেই, তাই prefix min দিয়ে range min হয় না।)

4. Real-life analogy¶

ভাবো একটা ঘরে কয়েকটা light switch — প্রতিটা toggle (টিপলে on↔off)। তুমি পরপর কতগুলো switch টিপলে, শেষে আলো জ্বলবে কি না সেটা জানতে চাও।

মজা হলো: একই switch দুবার টিপলে আগের অবস্থায় ফিরে যায় (on → off → on)। তাই "শুরু থেকে i পর্যন্ত মোট কতবার toggle" হিসাব রাখলে, যেকোনো মাঝের অংশের net toggle বের করা যায় — শুরুর অংশটা দুবার গুনে কেটে ফেলে।

এই "দুবার করলে কাটাকাটি" ধর্মটাই XOR-এর self-inverse। prefix XOR হলো "শুরু থেকে এ পর্যন্ত মোট toggle", আর range XOR হলো দুটো prefix XOR করে মাঝের net বের করা।

5. Visual explanation¶

a = [3, 5, 2, 7]। prefix XOR PX[i+1] = PX[i] ^ a[i]:

a   =   [ 3 ]  [ 5 ]  [ 2 ]  [ 7 ]
index     0      1      2      3

PX[0] = 0
PX[1] = 0 ^ 3 = 3
PX[2] = 3 ^ 5 = 6
PX[3] = 6 ^ 2 = 4
PX[4] = 4 ^ 7 = 3

PX  =   [ 0 ]  [ 3 ]  [ 6 ]  [ 4 ]  [ 3 ]
index     0      1      2      3      4

range XOR (l=1, r=2) চাই → a[1] ^ a[2] = 5 ^ 2 = 7:

PX[3] = a0 ^ a1 ^ a2        (= 3 ^ 5 ^ 2)
PX[1] = a0                  (= 3)
PX[3] ^ PX[1] = (a0 ^ a1 ^ a2) ^ a0
              = a1 ^ a2          ← a0 দুবার এসে কেটে গেল!
              = 5 ^ 2 = 7 ✓

মূল কথা: বাঁ অংশ a0 দুবার এল (একবার PX[3]-এ, একবার PX[1]-এ), তাই XOR-এ কেটে গেল। যা বাকি থাকল, সেটাই range-এর XOR। সংখ্যার বদলে XOR — কিন্তু "বাঁ অংশ বাদ" idea একই।

6. Example input and output¶

a = [3, 5, 2, 7],  PX = [0, 3, 6, 4, 3]

query (l, r)  ->  xor        কেন
-----------------------------------------------------
(1, 2)        ->  7          PX[3] ^ PX[1] = 4 ^ 3 = 7   (5 ^ 2)
(0, 3)        ->  3          PX[4] ^ PX[0] = 3 ^ 0 = 3   (পুরো array)
(2, 2)        ->  2          PX[3] ^ PX[2] = 4 ^ 6 = 2   (একটাই element)
(0, 0)        ->  3          PX[1] ^ PX[0] = 3 ^ 0 = 3
(1, 3)        ->  0          PX[4] ^ PX[1] = 3 ^ 3 = 0   (5 ^ 2 ^ 7 = 0)

Edge case: l = r হলে একটাই element-এর XOR (নিজেই)। আর লক্ষ করো (1, 3)-এ উত্তর 0 — কারণ 5 ^ 2 ^ 7 ঘটনাচক্রে 0; XOR-এ এমন cancellation স্বাভাবিক।

7. Brute force thinking¶

prefix না বানিয়ে, প্রতিটা query-তে loop চালিয়ে XOR জমাও:

def range_xor_brute(a, l, r):
    result = 0
    for i in range(l, r + 1):     # l থেকে r পর্যন্ত
        result ^= a[i]
    return result

সরল, ঠিক উত্তর দেয় — শুরুতে 0, তারপর range-এর প্রতিটা element XOR করে জমায়।

8. Why brute force may be slow¶

একটা query-তে loop চলে (r - l + 1) বার — খারাপ ক্ষেত্রে পুরো array, O(n)। q টা query হলে মোট O(n × q)।

n = 200000, q = 200000 হলে:
  brute force: ~4 × 10^10 operation  (O(n·q)) — TLE
  prefix way : O(n) build + q×O(1)   ≈ 4×10^5 — চোখের পলকে

range sum-এর মতোই অপচয়: overlapping query-তে একই অংশ বারবার XOR হচ্ছে। একই হিসাব বারবার = precompute-এর ডাক।

9. Better thinking¶

মূল insight: range XOR = দুটো prefix XOR-কে XOR করা। একবার prefix XOR PX বানাও (O(n)), তারপর প্রতিটা query এক XOR — O(1):

def build_prefix_xor(a):
    PX = [0] * (len(a) + 1)
    for i in range(len(a)):
        PX[i + 1] = PX[i] ^ a[i]
    return PX

def range_xor(PX, l, r):
    return PX[r + 1] ^ PX[l]       # O(1)

build একবার, query অসংখ্যবার সস্তায়। 068-এর হুবহু কাঠামো, শুধু - জায়গায় ^।

10. Thinking tweak¶

আসল "আহা!" মুহূর্ত: prefix কৌশল operator-এ আবদ্ধ নয় — যে operation-এর "undo" আছে, তাতেই চলে। যোগের undo বিয়োগ; XOR-এর undo XOR নিজেই (self-inverse)।

তাই 067-এর template থেকে range XOR পেতে নতুন কিছু ভাবার দরকার নেই — + কে ^ আর - কে ^ বানিয়ে দাও। এই "একই কাঠামো, ভিন্ন operator" চোখটা মূল্যবান: পরে min/max prefix কেন কাজ করে না সেটাও এই চোখেই বোঝা যায় (তাদের undo নেই)।

11. Step-by-step dry run¶

a = [3, 5, 2, 7], prefix XOR বানানো:

i	a[i]	PX[i]	PX[i+1] = PX[i] ^ a[i]
0	3	0	0 ^ 3 = 3
1	5	3	3 ^ 5 = 6
2	2	6	6 ^ 2 = 4
3	7	4	4 ^ 7 = 3

PX = [0, 3, 6, 4, 3]। এবার query (1, 2):

বড় prefix: PX[r+1] = PX[3] = 4 (a0 ^ a1 ^ a2)
ছোট prefix: PX[l] = PX[1] = 3 (a0)
XOR: 4 ^ 3 = 7
মিলিয়ে: a[1] ^ a[2] = 5 ^ 2 = 7 ✓ — বাঁয়ের a0=3 কেটে গেছে।

12. Python solution¶

def build_prefix_xor(a):
    """prefix XOR array; PX[i] = a[0] ^ ... ^ a[i-1], PX[0] = 0।"""
    PX = [0] * (len(a) + 1)
    for i in range(len(a)):
        PX[i + 1] = PX[i] ^ a[i]
    return PX


def range_xor(PX, l, r):
    """a[l..r] (দুই প্রান্ত সহ)-এর XOR, O(1)-এ।"""
    return PX[r + 1] ^ PX[l]


def range_xor_brute(a, l, r):
    """ধীর O(n) per query — মিলিয়ে দেখার জন্য।"""
    result = 0
    for i in range(l, r + 1):
        result ^= a[i]
    return result


# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [3, 5, 2, 7]
PX = build_prefix_xor(a)
assert PX == [0, 3, 6, 4, 3]

assert range_xor(PX, 1, 2) == 7      # 5 ^ 2
assert range_xor(PX, 0, 3) == 3      # পুরো array
assert range_xor(PX, 2, 2) == 2      # একটাই element
assert range_xor(PX, 0, 0) == 3
assert range_xor(PX, 1, 3) == 0      # 5 ^ 2 ^ 7 = 0

# fast আর brute সব (l, r)-এ একই উত্তর কিনা (brute-force cross-check):
import random
random.seed(11)
for _ in range(300):
    arr = [random.randint(0, 1023) for _ in range(random.randint(1, 12))]
    PXr = build_prefix_xor(arr)
    for l in range(len(arr)):
        for r in range(l, len(arr)):
            assert range_xor(PXr, l, r) == range_xor_brute(arr, l, r)

print(range_xor(PX, 1, 2))   # 7
print(range_xor(PX, 0, 3))   # 3
print("সব test pass!")

13. Line-by-line explanation¶

PX = [0] * (len(a) + 1)
for i in range(len(a)):
    PX[i + 1] = PX[i] ^ a[i]

prefix XOR build — 067-এর হুবহু কাঠামো, শুধু + জায়গায় ^। PX[0] = 0 sentinel (XOR-এর identity, কারণ x ^ 0 = x)।

def range_xor(PX, l, r):
    return PX[r + 1] ^ PX[l]

হৃদয়। PX[r+1] = index 0..r-এর XOR; PX[l] = index 0..l-1-এর XOR। দুটো XOR করলে বাঁ অংশ দুবার এসে কেটে যায়, থাকে l..r। এক XOR, O(1)।

result = 0
for i in range(l, r + 1):
    result ^= a[i]

ধীর brute — শুরুতে 0, range ধরে XOR জমায়। শুধু মিলিয়ে দেখার জন্য।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random array-তে সব (l, r) জোড়ায় fast আর brute মিলিয়ে দেখছে (brute-force cross-check)। সব মিললে সব test pass!।

14. Output walkthrough¶

a = [3, 5, 2, 7]:

range_xor(PX, 1, 2) → PX[3] ^ PX[1] = 4 ^ 3 = 7 → প্রথম print ছাপে 7
range_xor(PX, 0, 3) → PX[4] ^ PX[0] = 3 ^ 0 = 3 → দ্বিতীয় print ছাপে 3
সব assert চুপচাপ pass
শেষে সব test pass!

ছাপা output:

7
3
সব test pass!

15. Time complexity¶

Build O(n) (একবার), per query O(1) (একটা XOR)। মোট q query-তে O(n + q)। brute-এর O(n × q)-এর তুলনায় বিশাল লাভ — 068-এর সাথে হুবহু একই complexity।

16. Space complexity¶

O(n) — prefix XOR array PX রাখতে n+1 ঘর। query করতে আর বাড়তি জায়গা লাগে না, শুধু গুটিকয় variable।

17. Common mistakes¶

PX[r+1] - PX[l] লেখা (বিয়োগ) — XOR-এর undo বিয়োগ নয়, XOR নিজেই। সঠিক হলো PX[r+1] ^ PX[l]।
off-by-one — PX[r+1] ^ PX[l]; PX[r] ^ PX[l] দিলে a[r] বাদ পড়ে। sentinel convention মেনে চলো।
PX[0]-কে 0 ছাড়া কিছু বসানো — XOR-এর identity 0 (x ^ 0 = x); অন্য কিছু দিলে পুরো array shift হয়ে ভুল।
XOR-কে যোগ ভেবে ফেলা — 5 ^ 2 = 7 কাকতালীয়ভাবে 5 + 2-এর সমান, কিন্তু 5 ^ 3 = 6 ≠ 8। XOR carry ছাড়া bitwise; যোগ নয়।
range min/max-এ একই কৌশল চালানোর চেষ্টা — min/max-এর undo নেই, তাই prefix min দিয়ে range min হয় না। এই template শুধু invertible operation-এ।

18. Harder problems that inherit this idea¶

CSES — Range Xor Queries (https://cses.fi/problemset/task/1650) — ঠিক এই problem, অনেক query।
LeetCode — XOR Queries of a Subarray (https://leetcode.com/problems/xor-queries-of-a-subarray/) — হুবহু prefix XOR প্রয়োগ।
LeetCode — Count Triplets That Can Form Two Arrays of Equal XOR (https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/) — prefix XOR-এর গভীর প্রয়োগ।

19. Pattern learned¶

Prefix XOR for range XOR — PX[i+1] = PX[i] ^ a[i], range XOR = PX[r+1] ^ PX[l]। বড় শিক্ষা: prefix কৌশল operator-নিরপেক্ষ — যে operation invertible (যোগ↔বিয়োগ, XOR↔XOR), সেখানেই চলে; বিয়োগের জায়গায় XOR বসালেই হয়।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "range XOR = PX[r+1] ^ PX[l] (PX[0] = 0)। 067-এর template-ই, + → ^, - → ^ (XOR self-inverse)। prefix চলে যেকোনো invertible operation-এ।"

পরের ধাপ → 072 — 2D Prefix Sum (এক dimension থেকে দুই dimension-এ)।

ফিরে দেখা: শিকড় → 067 — Prefix Sum, 068 — Range Sum Query · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।