Problem link ও উৎস
- **Original source:** Classic technique (prefix XOR for range XOR queries)
- **Platform:** CSES Range Xor Queries —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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)**-এ দিতে হবে।
### Input ও output {#6-example-input-and-output}
```text
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 স্বাভাবিক।
### চেনা উদাহরণে বোঝা {#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 বের করা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 হয় না।)
### ভেতরের অঙ্ক {#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:
```text
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-এ করছে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
prefix না বানিয়ে, প্রতিটা query-তে loop চালিয়ে XOR জমাও:
```python
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)**।
```text
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):
```python
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 নেই)।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [3, 5, 2, 7]`। prefix XOR `PX[i+1] = PX[i] ^ a[i]`:
```text
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 একই।
### ছোট input-এ ধাপে ধাপে {#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)`:
1. বড় prefix: `PX[r+1] = PX[3] = 4` (a0 ^ a1 ^ a2)
2. ছোট prefix: `PX[l] = PX[1] = 3` (a0)
3. XOR: `4 ^ 3 = 7`
4. মিলিয়ে: `a[1] ^ a[2] = 5 ^ 2 = 7` ✓ — বাঁয়ের `a0=3` কেটে গেছে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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`)।
```text
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)।
```text
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!`।
### Output মিলিয়ে দেখা {#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:
```text
7
3
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **`PX[r+1] - PX[l]` লেখা (বিয়োগ)** — XOR-এর undo বিয়োগ নয়, XOR নিজেই। সঠিক হলো `PX[r+1] ^ PX[l]`।
2. **off-by-one** — `PX[r+1] ^ PX[l]`; `PX[r] ^ PX[l]` দিলে `a[r]` বাদ পড়ে। sentinel convention মেনে চলো।
3. **`PX[0]`-কে 0 ছাড়া কিছু বসানো** — XOR-এর identity 0 (`x ^ 0 = x`); অন্য কিছু দিলে পুরো array shift হয়ে ভুল।
4. **XOR-কে যোগ ভেবে ফেলা** — `5 ^ 2 = 7` কাকতালীয়ভাবে `5 + 2`-এর সমান, কিন্তু `5 ^ 3 = 6 ≠ 8`। XOR carry ছাড়া bitwise; যোগ নয়।
5. **range min/max-এ একই কৌশল চালানোর চেষ্টা** — min/max-এর undo নেই, তাই prefix min দিয়ে range min হয় না। এই template শুধু invertible operation-এ।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Range Xor Queries** (