對數組的范圍查詢，其每個元素都是索引值與前一個元素的 XOR · GeeksForGeeks 中文系列教程

# 對數組的范圍查詢，其每個元素都是索引值與前一個元素的 XOR > 原文： [https://www.geeksforgeeks.org/range-query-array-whose-element-xor-index-value-previous-element/](https://www.geeksforgeeks.org/range-query-array-whose-element-xor-index-value-previous-element/) 考慮一個 **arr []** ，它可以定義為： ![](https://img.kancloud.cn/8e/a0/8ea0eb51420968191e07fc58f1bc7ccc_300x123.png) 給您 **Q** 查詢，形式為 **[l，r]** 。任務是為每個查詢輸出 arr [l]⊕arr [l + 1]……..⊕arr [r-1]⊕arr [r]的值。 **示例**： ``` Input : q = 3 q1 = { 2, 4 } q2 = { 2, 8 } q3 = { 5, 9 } Output : 7 9 15 The beginning of the array with constraint look like: arr[] = { 0, 1, 3, 0, 4, 1, 7, 0, 8, 1, 11, .... } For q1, 3 ⊕ 0 ⊕ 4 = 7 For q2, 3 ⊕ 0 ⊕ 4 ⊕ 1 ⊕ 7 ⊕ 0 ⊕ 8 = 9 For q3, 1 ⊕ 7 ⊕ 0 ⊕ 8 ⊕ 1 = 15 ``` 讓我們觀察 **arr []** ``` arr[0] = 0 arr[1] = 1 arr[2] = 1 ⊕ 2 arr[3] = 1 ⊕ 2 ⊕ 3 arr[4] = 1 ⊕ 2 ⊕ 3 ⊕ 4 arr[5] = 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 .... ``` 讓我們創建另一個數組，例如 brr []，其中 brr [i] = arr [0]⊕arr [1]⊕arr [2]…..⊕arr [i]。 brr [i] = arr [0]⊕arr [1]⊕arr [2]……arr [i-1]⊕arr [i] = brr [j]⊕arr [j + 1]⊕arr [j + 2]⊕.....⊕arr [i]，對于任何 0 < = j < = i。因此，arr [l] = arr [l + 1] ..... arr [r] = brr [l-1] = brr [r]。現在，讓我們觀察一下 brr []： ``` brr[1] = 1 brr[2] = 2 brr[3] = 1 ⊕ 3 brr[4] = 2 ⊕ 4 brr[5] = 1 ⊕ 3 ⊕ 5 brr[6] = 2 ⊕ 4 ⊕ 6 brr[7] = 1 ⊕ 3 ⊕ 5 ⊕ 7 brr[8] = 2 ⊕ 4 ⊕ 6 ⊕ 8 ``` 很容易觀察到，在奇數索引中 brr [i] = 1⊕3⊕5⊕…。對于偶數索引 brr [i] = 2 4 6 6…。 ⊕我對于偶數索引，有從 1 到 i / 2 乘以 2 的數字，這意味著位將向左移動 1，因此 brr [i] = 2 4 4 6…。 ⊕i =（1⊕2⊕3…..⊕i / 2）*2。對于奇數索引，從 0 到（i – 1）/ 2 的數字乘以 2 加 1。位左移 1，最后一位為 1。因此，brr [i] = 1 3 3 5…。 ⊕i =（0⊕1⊕2⊕…。⊕（i – 1）/ 2）* 2 + x。 x 是 1⊕1。…..⊕1“ 1”重復（i – 1）/ 2 + 1 次。因此，如果（i-1）/ 2 +1 為奇數，則 x = 1，否則 x = 0。現在，計算 1⊕2⊕3⊕…。 ⊕x。讓我們證明（4K）⊕（4K + 1）⊕（4K + 2）⊕（4K + 3）= 0，< = k。 ``` bitmask(K)00=4K xorsum bitmask(K)01=4K+1 bitmask(K)10=4K+2 bitmask(K)11=4k+3 --------------------- 000000000000=0 ``` 因此，當 0⊕Y = Y 時，則 1⊕2⊕3⊕…x =（floor（x / 4）x 4）…⊕x 這里最多有 3 個數字，因此我們可以在`O(1)`中進行計算。下面是此方法的實現： ## C++ ```cpp // CPP Program to solve range query on array // whose each element is XOR of index value // and previous element. #include <bits/stdc++.h> using namespace std; // function return derived formula value. int fun(int x) { ????int y = (x / 4) * 4; ????// finding xor value of range [y...x] ????int ans = 0; ????for (int i = y; i <= x; i++) ????????ans ^= i; ????return ans; } // function to solve query for l and r. int query(int x) { ????// if l or r is 0\. ????if (x == 0) ????????return 0; ????int k = (x + 1) / 2; ????// finding x is divisible by 2 or not. ????return (x %= 2) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } void allQueries(int q, int l[], int r[]) { ????for (int i = 0; i < q; i++) ????????cout << (query(r[i]) ^ query(l[i] - 1)) << endl; } // Driven Program int main() { ????int q = 3; ????int l[] = { 2, 2, 5 }; ????int r[] = { 4, 8, 9 }; ????allQueries(q, l, r); ????return 0; } ``` ## Java ```java // Java Program to solve range query on array // whose each element is XOR of index value // and previous element. import java.io.*; class GFG { ????// function return derived formula value. ????static int fun(int x) ????{ ????????int y = (x / 4) * 4; ????????// finding xor value of range [y...x] ????????int ans = 0; ????????for (int i = y; i <= x; i++) ????????????ans ^= i; ????????return ans; ????} ????// function to solve query for l and r. ????static int query(int x) ????{ ????????// if l or r is 0\. ????????if (x == 0) ????????????return 0; ????????int k = (x + 1) / 2; ????????// finding x is divisible by 2 or not. ????????return ((x %= 2) != 0) ? 2 * fun(k) :? ???????????????????((fun(k - 1) * 2) ^ (k & 1)); ????} ????static void allQueries(int q, int l[], int r[]) ????{ ????????for (int i = 0; i < q; i++) ????????????System.out.println((query(r[i]) ^? ???????????????????????????????query(l[i] - 1))) ; ????} ????// Driven Program ????public static void main (String[] args) { ????????int q = 3; ????????int []l = { 2, 2, 5 }; ????????int []r = { 4, 8, 9 }; ????????allQueries(q, l, r); ????} } // This code is contributed by vt_m. ``` ## Python3 ```py # Python3 Program to solve range query? # on array whose each element is XOR of? # index value and previous element.? # function return derived formula value.? def fun(x): ????y = (x // 4) * 4 ????# finding xor value of range [y...x]? ????ans = 0 ????for i in range(y, x + 1): ????????ans ^= i? ????return ans # function to solve query for l and r.? def query(x): ????# if l or r is 0.? ????if (x == 0):? ????????return 0 ????k = (x + 1) // 2 ????# finding x is divisible by 2 or not.? ????if x % 2 == 0: ????????return((fun(k - 1) * 2) ^ (k & 1)) ????else: ????????return(2 * fun(k)) def allQueries(q, l, r):? ????for i in range(q): ????????print(query(r[i]) ^ query(l[i] - 1)) # Driver Code q = 3 l = [ 2, 2, 5 ]? r = [ 4, 8, 9 ]? allQueries(q, l, r)? # This code is contributed? # by sahishelangia ``` ## C# ```cs // C# Program to solve range query on array // whose each element is XOR of index value // and previous element. using System; class GFG { ????// function return derived formula value. ????static int fun(int x) ????{ ????????int y = (x / 4) * 4; ????????// finding xor value of range [y...x] ????????int ans = 0; ????????for (int i = y; i <= x; i++) ????????????ans ^= i; ????????return ans; ????} ????// function to solve query for l and r. ????static int query(int x) ????{ ????????// if l or r is 0\. ????????if (x == 0) ????????????return 0; ????????int k = (x + 1) / 2; ????????// finding x is divisible by 2 or not. ????????return ((x %= 2)!=0) ? 2 * fun(k) :? ???????????????????((fun(k - 1) * 2) ^ (k & 1)); ????} ????static void allQueries(int q, int []l, int []r) ????{ ????????for (int i = 0; i < q; i++) ????????????Console.WriteLine((query(r[i])? ??????????????????????????????^ query(l[i] - 1))) ; ????} ????// Driven Program ????public static void Main () ????{ ????????int q = 3; ????????int []l = { 2, 2, 5 }; ????????int []r = { 4, 8, 9 }; ????????allQueries(q, l, r); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // PHP Program to solve range? // query on array whose each? // element is XOR of index? // value and previous element. // function return derived // formula value. function fun($x) { ????$y = ((int)($x / 4) * 4); ????// finding xor value? ????// of range [y...x] ????$ans = 0; ????for ($i = $y; $i <= $x; $i++) ????????$ans ^= $i; ????return $ans; } // function to solve? // query for l and r. function query($x) { ????// if l or r is 0\. ????if ($x == 0) ????????return 0; ????$k = (int)(($x + 1) / 2); ????// finding x is divisible ????// by 2 or not. ????return ($x %= 2) ? 2 * fun($k) :? ?????((fun($k - 1) * 2) ^ ($k & 1)); } function allQueries($q, $l, $r) { ????for ($i = 0; $i < $q; $i++) ????????echo (query($r[$i]) ^? ??????????????query($l[$i] - 1)) , "\n"; } // Driver Code $q = 3; $l = array( 2, 2, 5 ); $r = array ( 4, 8, 9 ); allQueries($q, $l, $r); // This code is contributed by ajit ?> ``` **輸出**： ``` 0 2 0 ``` * * * * * *