Problem link ও উৎস
- **Original source:** CSES Problem Set — Range Queries section
- **Platform:** CSES Problem Set — "Range Xor Queries" —
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Medium
- **Pattern:** prefix xor / invertible ops (static range, tree লাগে না)
- **Basic idea inherited from:** math level 4 xor, prefix idea
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n`-টা সংখ্যার একটা array আর `q`-টা query। প্রতিটা query-তে দুটো index `a` আর `b`; তোমাকে `a` থেকে `b` পর্যন্ত (দুই প্রান্ত সহ) সব element-এর **xor** (`^`) বলতে হবে। array কখনো বদলায় না — পুরোপুরি static।
```text
array = [3, 2, 4, 5, 1, 1, 5, 3]
query a=2, b=4 -> 2 ^ 4 ^ 5 = 3
query a=5, b=6 -> 1 ^ 1 = 0
```
### Input ও output {#8-example-input-and-output}
```text
Input:
n = 8, q = 2
array = [3, 2, 4, 5, 1, 1, 5, 3]
query 2 4
query 5 6
Output:
3
0
Edge case 1 (একটা element): a=3, b=3 -> 4
Edge case 2 (xor নিজেকে বাতিল): a=5, b=6 -> 1 ^ 1 = 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো প্রতিটা ঘরে একটা করে light switch, আর তুমি একটা খাতায় লিখে রাখছ "শুরু থেকে এ পর্যন্ত প্রতিটা switch কতবার টেপা হলে, তার সম্মিলিত on/off অবস্থা"। দুটো switch একই অবস্থায় থাকলে তারা একে অপরকে বাতিল করে (`x ^ x = 0`)। তাই কোনো একটা অংশের সম্মিলিত অবস্থা জানতে, শুরুর checkpoint-কে শেষের checkpoint দিয়ে xor করলেই মাঝের অংশটা বেরিয়ে আসে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দুটো ভিতের উপর দাঁড়িয়ে: math level 4-এর **xor** আর math level 5-এর **prefix idea** ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। মূল চিন্তা problem #1-এর প্রায় হুবহু — শুধু `+` (এবং `-`)-এর জায়গায় `^`।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **xor-ও invertible — আসলে এটা তার নিজেরই inverse** (`x ^ x = 0`, `x ^ 0 = x`)। তাই sum-এর মতোই prefix-xor কাজ করে: `prefixXor[i]` = প্রথম `i`-টা element-এর xor হলে, `xor(a..b) = prefixXor[b] ^ prefixXor[a-1]`। বিয়োগের বদলে আবার xor — কারণ xor নিজেই উল্টোটা ফিরিয়ে দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
শুধু **একটা prefix-xor array**। আবার, topic-এর নাম tree হলেও static array-তে tree লাগে না; xor invertible বলে prefix trick-ই যথেষ্ট আর দ্রুততম।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
কোনো update নেই, আর xor invertible — দুই শর্তই prefix-array-র পক্ষে। build O(n), প্রতি query O(1)। এখানে segment tree বানানো over-engineering; Fenwick বানানোও অপ্রয়োজনীয়, কারণ update নেই। static + invertible = prefix array, সবচেয়ে সরল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা query-তে `a` থেকে `b` loop চালিয়ে চলমান xor রাখা।
```text
for each query (a, b):
x = 0
for i in range(a, b+1):
x ^= array[i]
print(x)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা query O(n), q-টা query মিশলে O(n·q)। CSES-এ n, q দুটোই 2×10^5 পর্যন্ত — প্রায় 4×10^10 operation, TLE। একই অংশ বারবার xor করাটা অপচয়, যখন একবার prefix-xor বানিয়েই কাজ চলে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **xor self-inverse** (`x ^ x = 0`)। তাই `xor(a..b) = X[b] ^ X[a-1]` — বাঁ দিকের prefix-টা xor করলে নিজে নিজে বাতিল হয়ে যায়, বাকি থাকে ঠিক চাওয়া অংশ। একবার prefix-xor সাজালে প্রতিটা query একটা মাত্র xor।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
শুরুতে O(n)-এ prefix-xor array বানাও (`X[i] = X[i-1] ^ a[i]`)। তারপর প্রতিটা query-তে `X[b] ^ X[a-1]` return করো — O(1)। মোট O(n + q)। sum-এর সাথে একমাত্র পার্থক্য: বিয়োগের জায়গায় xor, sentinel-ও `0` (xor-এর identity, ঠিক sum-এর মতো)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "range xor" দেখে নতুন structure ভাবার দরকার নেই — আগে জিজ্ঞেস করো *"operation কি invertible? update আছে?"*। xor invertible, update নেই → ঠিক prefix sums-এর জমজ, শুধু `+`→`^`, `-`→`^`। invertible operation চিনতে পারাটাই এখানে আসল দক্ষতা।
### ছবিতে বোঝা {#7-visual-explanation}
`a = [3, 2, 4, 5, 1, 1, 5, 3]`-এর prefix-xor array `X` (sentinel `X[0]=0`):
```text
index : 0 1 2 3 4 5 6 7 8
a : 3 2 4 5 1 1 5 3
X : 0 3 1 5 0 1 0 5 6
running xor (X[i] = X[i-1] ^ a[i])
query a=2, b=4:
X = [0, 3, 1, 5, 0, 1, 0, 5, 6]
^X[1] ^X[4]
xor = X[b] ^ X[a-1] = X[4] ^ X[1] = 0 ^ 3 = 3
(= 2 ^ 4 ^ 5, correct)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`[3, 2, 4, 5, 1, 1, 5, 3]`, query `(2, 4)`:
1. prefix-xor বানাও: `X = [0, 3, 1, 5, 0, 1, 0, 5, 6]`।
2. query `(a=2, b=4)` এসেছে।
3. `X[b] = X[4] = 0`।
4. `X[a-1] = X[1] = 3`।
5. উত্তর = `0 ^ 3 = 3` → এটাই `2 ^ 4 ^ 5`, ঠিক আছে।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class PrefixXor:
"""Static array-র উপর O(1) range xor। xor self-inverse (x ^ x = 0),
তাই prefix sums-এর মতোই prefix-xor কাজ করে — কোনো tree লাগে না।"""
def __init__(self, data):
# X[i] = প্রথম i-টা element-এর xor; X[0] = 0 (xor identity)
self.X = [0] * (len(data) + 1)
for i, v in enumerate(data):
self.X[i + 1] = self.X[i] ^ v
def range_xor_1indexed(self, a, b):
# 1-indexed inclusive [a, b]: বিয়োগের বদলে আবার xor
return self.X[b] ^ self.X[a - 1]
def brute(data, a, b):
# 1-indexed inclusive, obviously-correct reference
x = 0
for v in data[a - 1:b]:
x ^= v
return x
# ---- tests ----
data = [3, 2, 4, 5, 1, 1, 5, 3]
px = PrefixXor(data)
assert px.range_xor_1indexed(2, 4) == 3 # 2 ^ 4 ^ 5
assert px.range_xor_1indexed(5, 6) == 0 # 1 ^ 1 (self-cancel)
assert px.range_xor_1indexed(3, 3) == 4 # একটা element
assert px.range_xor_1indexed(1, 8) == brute(data, 1, 8) # পুরো array
# brute force-এর সাথে exhaustively মিলিয়ে দেখা
for a in range(1, len(data) + 1):
for b in range(a, len(data) + 1):
assert px.range_xor_1indexed(a, b) == brute(data, a, b)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.X = [0]*(len(data)+1)` — n+1 ঘর, `X[0]=0` (xor-এর identity, sentinel)।
- `self.X[i + 1] = self.X[i] ^ v` — running xor, আগের prefix-এর সাথে এই element xor।
- `range_xor_1indexed(a, b)` — `X[b] ^ X[a-1]`; বিয়োগ নয়, কারণ xor নিজেই উল্টোটা।
- `brute` — slow কিন্তু স্পষ্টভাবে সঠিক reference, fast version verify করতে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`PrefixXor([3,2,4,5,1,1,5,3])` বানায় `X = [0,3,1,5,0,1,0,5,6]`। `range_xor_1indexed(2,4)` দেয় `X[4]^X[1]=0^3=3`, `(5,6)` দেয় `0^0=0` (1^1 বাতিল) — সব assert pass। double loop সব `(a,b)` brute-এর সাথে মেলায়। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**Build O(n)** (একবার prefix-xor), **প্রতি query O(1)**। মোট O(n + q)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — n+1 ঘরের prefix-xor array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `X[b] ^ X[a]` লেখা — `X[a-1]` দরকার, নাহলে `a` নম্বর element বাদ যায়।
- xor-এর জায়গায় ভুলে `-` (subtraction) ব্যবহার করা — xor-এর inverse xor নিজেই, বিয়োগ নয়।
- Static + invertible জেনেও segment tree বানানো — অপ্রয়োজনীয়; prefix array-ই যথেষ্ট।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: math level 4-এর xor + math level 5-এর prefix idea ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। problem #1-এর সাথে প্রায় যমজ, শুধু operation বদলানো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Static Range Sum Queries (একই idea, `+` দিয়ে) —