008 — Range Xor Queries¶

Source¶

Original source: CSES Problem Set — Range Queries section
Platform: CSES Problem Set — "Range Xor Queries" — https://cses.fi/problemset/
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

1. Problem in simple words¶

n-টা সংখ্যার একটা array আর q-টা query। প্রতিটা query-তে দুটো index a আর b; তোমাকে a থেকে b পর্যন্ত (দুই প্রান্ত সহ) সব element-এর xor (^) বলতে হবে। array কখনো বদলায় না — পুরোপুরি static।

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

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/)। মূল চিন্তা 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, সবচেয়ে সরল।

6. Real-life analogy¶

ভাবো প্রতিটা ঘরে একটা করে light switch, আর তুমি একটা খাতায় লিখে রাখছ "শুরু থেকে এ পর্যন্ত প্রতিটা switch কতবার টেপা হলে, তার সম্মিলিত on/off অবস্থা"। দুটো switch একই অবস্থায় থাকলে তারা একে অপরকে বাতিল করে (x ^ x = 0)। তাই কোনো একটা অংশের সম্মিলিত অবস্থা জানতে, শুরুর checkpoint-কে শেষের checkpoint দিয়ে xor করলেই মাঝের অংশটা বেরিয়ে আসে।

7. Visual explanation¶

a = [3, 2, 4, 5, 1, 1, 5, 3]-এর prefix-xor array X (sentinel X[0]=0):

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] = a[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)

8. Example input and output¶

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা query-তে a থেকে b loop চালিয়ে চলমান xor রাখা।

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 চিনতে পারাটাই এখানে আসল দক্ষতা।

14. Step-by-step dry run¶

[3, 2, 4, 5, 1, 1, 5, 3], query (2, 4):

prefix-xor বানাও: X = [0, 3, 1, 5, 0, 1, 0, 5, 6]।
query (a=2, b=4) এসেছে।
X[b] = X[4] = 0।
X[a-1] = X[1] = 3।
উত্তর = 0 ^ 3 = 3 → এটাই 2 ^ 4 ^ 5, ঠিক আছে।

15. Python solution¶

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 করতে।

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!।

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-ই যথেষ্ট।

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/)। problem #1-এর সাথে প্রায় যমজ, শুধু operation বদলানো।

22. Similar harder problems¶

Static Range Sum Queries (একই idea, + দিয়ে) — https://cses.fi/problemset/task/1646 (এই tracker-এর #1)
Dynamic Range Sum Queries (update যোগ হলে tree লাগে) — https://cses.fi/problemset/task/1648 (#6)
Dynamic Range Minimum Queries (min — invertible নয়, segment tree লাগে) — CSES "Dynamic Range Minimum Queries" (#7)

23. Pattern learned¶

Prefix xor / invertible ops: static array-তে যেকোনো invertible operation (sum, xor) prefix array দিয়ে O(1) range query দেয়। বড় শিক্ষা: invertibility থাকলে prefix trick চলে; না থাকলে (min/max) segment tree লাগে।

24. Final summary¶

ভবিষ্যতের আমাকে: range query-তে দুটো প্রশ্ন আগে — "update আছে? operation invertible?"। দুটোই static + invertible (sum, xor) হলে prefix array, tree নয়। xor-এর জাদু হলো এটা নিজেই নিজের inverse, তাই বিয়োগের বদলে আবার xor। এই pattern চিনে নিলে #1 আর #8 একই reflex-এর দুই রূপ।

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