Lazy Propogation with Xor range updates and range sum queries

Revision en7, by one_autum_leaf, 2024-10-05 13:19:14

Problem Statement:

You are given an array arr of size $$$N$$$. Initially, all $$$arr[i]$$$ are set to 0. Now consider $$$Q$$$ queries, where each query is of one of the following two types:

  1. [1, l, r]: In this case, calculate the sum of values of $$$arr[i]$$$ for $$$l \le i \le r$$$.
  2. [2, l, r, x]: In this case, for each $$$arr[i]$$$, $$$l \le i \le r$$$, update the value to $$$arr[i] = arr[i] \oplus x$$$ (where $$$\oplus$$$ is the XOR operation).

Constraints:

  1. $$$ 1 \le N \le 10^5 $$$
  2. $$$ 1 \le Q \le 10^5 $$$
  3. $$$ 1 \le l \le r \le N $$$
  4. $$$ 1 \le x \le 2^{30} - 1 $$$

Approach:

This problem can be solved easily with a Segment Tree with Lazy Propagation, had there been no XOR updates. Lazy Propagation requires that for an update on range $$$[l, r]$$$, we should be able to calculate the value of $$$[l, r]$$$ after the update in $$$O(1)$$$ time (or at least sub-linear time like $$$O(\log n)$$$).

For other updates, say multiply by $$$x$$$, this would be simple. The value of $$$[l, r]$$$ after the update would be:

new_sum = x * prev_sum

For XOR updates, though, this is not so straightforward.


Simplifying the XOR Update

Generalizing for the Full Problem:

Code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English one_autum_leaf 2024-10-06 09:42:25 0 (published)
en9 English one_autum_leaf 2024-10-06 09:41:52 8073 Tiny change: ' - 1 $\n\n[problem:2' -> ' - 1 $\n\nProblem Link - [problem:2' (saved to drafts)
en8 English one_autum_leaf 2024-10-05 13:20:13 6 (published)
en7 English one_autum_leaf 2024-10-05 13:19:14 195 Tiny change: 'e">\n~~~~~\n\n#inclu' -> 'e">\n~~~~~cpp\n\n#inclu' (saved to drafts)
en6 English one_autum_leaf 2024-10-05 13:15:14 371 Tiny change: ' <= x <= 2^{30} &mdash; 1\)\n\n--' -> ' <= x <= 2_30 - 1\)\n\n--' (published)
en5 English one_autum_leaf 2024-10-05 12:57:05 2408
en4 English one_autum_leaf 2024-10-05 12:52:00 2158
en3 English one_autum_leaf 2024-10-05 12:51:31 1405 Tiny change: '```\nConsider' -> '```text\nConsider'
en2 English one_autum_leaf 2024-10-05 12:33:03 541
en1 English one_autum_leaf 2024-10-05 12:28:59 4585 Initial revision (saved to drafts)