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 — l + 1 — 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.

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}$$$

1. 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.

#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;
}