Lazy Propogation with Xor range updates and range sum queries
Difference between en9 and en10, changed 0 character(s)
### 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 $↵

Problem Link — [problem:242E]↵

---↵

### 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.↵

---↵

<spoiler summary="Simplifying the XOR Update">↵
### Simplifying the XOR Update:↵

Consider a simpler problem. Let's say that all values in `arr` can be either 0 or 1, and even $x$ can be only 0 or 1.↵

Now the sum of range $[l, r]$ is $S$, which indicates that there are $S$ 1s and $r &mdash; l + 1 &mdash; S$ 0s in $[l, r]$.↵

1. An update with $x = 0$ won’t change anything.↵
2. An update with $x = 1$ would flip 0s and 1s, so there will be $r - l + 1 - S $ 1s and $S$ 0s. The new sum is:↵


$r - l + 1 - S $↵

Thus, we can build a segment tree with lazy propagation for this array.↵
</spoiler>↵

---↵

<spoiler summary="Generalizing for the Full Problem:">↵
### Generalizing for the Full Problem:↵

The key idea is to notice that each number can be at most 30 bits, and we can just maintain such arrays for each of the 30 bits.↵

So, we build $LOGMAX (=30)$ such arrays, and for each query:↵

1. For sum $[l, r]$, calculate ${sum}_0, \text{sum}_1, \ldots, \text{sum}_{29}$ for each of the trees. The final sum is:↵


$\text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29}$↵

2. For the update $[l, r]$ with XOR $x$, flip $[l, r]$ for the $k^{th}$ tree if the $k^{th}$ bit of $x$ is set.↵
</spoiler>↵

--- ↵

<spoiler summary="Code">↵
~~~~~↵

#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
struct LazySegmentTree {↵
    const int LOGMAX = 30;↵
    int n;↵
    vector<int> lazy;↵
    vector<vector<int>> sum;↵
    vector<int> L, R;↵

    LazySegmentTree(vector<int>& arr) {↵
        int sz = arr.size();↵
        n = 1;↵
        while (n < sz) n <<= 1;↵
        lazy.assign(2 * n, 0);↵
        sum.assign(2 * n, vector<int>(LOGMAX, 0));↵
        L.assign(2 * n, 0);↵
        R.assign(2 * n, 0);↵


        // Initialize the segment tree leaves↵
        for (int i = 0; i < sz; ++i) {↵
            for (int k = 0; k < LOGMAX; ++k) {↵
                sum[i + n][k] = (arr[i] >> k) & 1;↵
            }↵
        }↵
        for(int i = 0; i < n; ++i){↵
            L[i + n] = R[i + n] = i;↵
        }↵

        // Build the segment tree↵
        for (int i = n - 1; i > 0; --i) {↵
            for (int k = 0; k < LOGMAX; ++k) {↵
                sum[i][k] = sum[2 * i][k] + sum[2 * i + 1][k];↵
            }↵
            L[i] = L[2 * i];↵
            R[i] = R[2 * i + 1];↵
        }↵
    }↵

    void apply(int node, int x) {↵
        for (int k = 0; k < LOGMAX; ++k) {↵
            if (x & (1 << k)) {↵
                sum[node][k] = (R[node] - L[node] + 1) - sum[node][k];↵
            }↵
        }↵
        if (node < n) {↵
            lazy[node] ^= x;↵
        }↵
    }↵

    void propagate(int node) {↵
        if (lazy[node]) {↵
            apply(2 * node, lazy[node]);↵
            apply(2 * node + 1, lazy[node]);↵
            lazy[node] = 0;↵
        }↵
    }↵

    void update(int node) {↵
        for (int k = 0; k < LOGMAX; ++k) {↵
            sum[node][k] = sum[2 * node][k] + sum[2 * node + 1][k];↵
        }↵
    }↵

    void rangeUpdate(int l, int r, int x) {↵
        l += n;↵
        r += n;↵
        int l0 = l, r0 = r;↵

        // Apply any existing lazy updates↵
        for (int i = __lg(n); i >= 1; --i) {↵
            if ((l >> i) > 0) propagate(l >> i);↵
            if ((r >> i) > 0) propagate(r >> i);↵
        }↵

        // Update the segment tree↵
        for (; l <= r; l >>= 1, r >>= 1) {↵
            if (l & 1) apply(l++, x);↵
            if (!(r & 1)) apply(r--, x);↵
        }↵

        // Update affected parent nodes↵
        for (l = l0 >> 1; l > 0; l >>= 1) propagate(l), update(l);↵
        for (r = r0 >> 1; r > 0; r >>= 1) propagate(r), update(r);↵
    }↵


    long long rangeQuery(int l, int r) {↵
        l += n;↵
        r += n;↵
        long long res = 0;↵

        // Apply any existing lazy updates↵
        for (int i = __lg(n); i >= 1; --i) {↵
            if ((l >> i) > 0) propagate(l >> i);↵
            if ((r >> i) > 0) propagate(r >> i);↵
        }↵

        // Query the segment tree↵
        for (; l <= r; l >>= 1, r >>= 1) {↵
            if (l & 1) res += getSum(l++);↵
            if (!(r & 1)) res += getSum(r--);↵
        }↵

        return res;↵
    }↵

    long long getSum(int node) {↵
        long long result = 0;↵
        for (int k = 0; k < LOGMAX; ++k) {↵
            result += (1LL << k) * sum[node][k];↵
        }↵
        return result;↵
    }↵
};↵
 ↵
int main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0); cout.tie(0);↵
 ↵
    int n;↵
    cin >> n;↵
    vector<int> a(n + 1);↵
    for(int i = 1; i <= n; ++i){↵
        cin >> a[i];↵
    }↵

    LazySegmentTree tree(a);↵

    int q;↵
    cin >> q;↵
    while(q--){↵
        int type, l, r;↵
        cin >> type >> l >> r;↵
        if(type == 1){↵
            cout << tree.rangeQuery(l, r) << '\n';↵
        }↵
        else{↵
            int x;↵
            cin >> x;↵
            tree.rangeUpdate(l, r, x);↵
        }↵
    }↵
    return 0;↵
}↵
 ↵
~~~~~↵
</spoiler>↵

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)