Найдите окончательный массив, обновив заданные диапазоны

Учитывая массив arr[] , состоящий из N целых чисел, и массив Q[][3 ], состоящий из M запросов вида [L, R, U] , задача для каждого запроса состоит в том, чтобы выполнить операцию xor для каждого элемента массива в диапазоне [L , R] с U, После обработки каждого запроса выведите окончательный массив.

Примеры:

Input: arr[] = {0, 0, 0, 0, 0, 0, 0}, Q[][] = {{2, 4, 1}, {0, 4, 2}, {1, 5, 3}}
Output: Initial Array : 0  0  0  0  0  0  0  
Final Array : 2  1  0  0  0  3  0 
Explanation: Query 1: For query {2, 4, 1} xor every index from 2 to 4 with 1 so it becomes {0, 0, 1, 1, 1, 0, 0}
Query 2: For query {0, 4, 2} xor every index from 0 to 4 with 2 so it becomes {2, 2, 1 ^ 2, 1 ^ 2, 1 ^ 2, 0, 0} which is {2, 2, 3, 3, 3, 0, 0}
Query 3: For query {1, 5, 3} xor every index from 1 to 5 with 3 so it becomes {2, 2 ^ 3, 1 ^ 2 ^ 3, 1 ^ 2 ^ 3, 1 ^ 2 ^ 3, 3, 0} which is {2, 1, 0, 0, 0, 3, 0}

Input: arr[] = {1, 2, 4, 3, 9}, Q[][] = {{0, 3, 15}, {0, 4, 15}}
Output: Initial Array : 1  2  4  3  9  
Final Array : 14  13  11  12  6

Наивный подход: основной способ решения проблемы заключается в следующем:

Iterate from L to R and xor U to all elements from arr[L] to arr[R] for each query.

Временная сложность: O(N * M), где M — количество запросов.
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход может быть оптимизирован на основе следующей идеи:

We can utilise prefix xor (similar to prefix sum) efficiently to be able to perform following queries in constant time. Idea is if we take xor of prefix[L] with U and xor of prefix[R + 1] with U again after doing prefix XOR we can observe that L to R gets updated with xor with U. But when we try to take xor at R + 1 XOR that was carrying itself forward from L in prefix xor gets deleted at R + 1 (since x ^ x == 0).

For Example: {0, 0, 0, 0, 0} and L = 1, R = 3 and U = 10

Updating array at L and R + 1 with U: {0, 10, 0, 0, 10}

• STEP 1: {0, 10, 0, 0, 10}
• STEP 2: {0, 10, 10, 0, 10}
• STEP 3: {0, 10, 10, 10, 10}
• STEP 4: {0, 10, 10, 10, 10 ^ 10} that is {0, 10, 10, 10, 0}

This can be observed that 10 was carrying itself forward but at R + 1 it gets deleted and range from L to R  gets updated with xor U. This can be used for all queries.

Выполните следующие шаги, чтобы решить проблему:

• Определен префикс массива перед вычислением []
• Обход для каждого запроса M и взятие xor префикса [L] с U и префикса [R + 1] с U.
• Использование префикса xor для каждого U для M запросов переносится от L к R и заканчивается на R + 1 .
• Берем xor соответствующих индексов исходного массива с массивом префиксов и затем печатаем его.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N + M)
Вспомогательное пространство: O(N)