题意

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。我们需要支持两种操作：

1. 查询区间 $[l, r]$ 的和；
2. 将区间 $[l, r]$ 中的每个数异或上一个给定的数 $x$。

思路

将每个数 $a_i$ 拆成 $20$ 个二进制位，形成一个 $n \times 20$ 的表格 $b_{i,j}$，其中 $b_{i,j}$ 表示 $a_i$ 的第 $j$ 位。
那么区间 $[l, r]$ 的和可以表示为：

$$\sum_{i=l}^{r} a_i = \sum_{j=0}^{19} 2^j \cdot \left( \sum_{i=l}^{r} b_{i,j} \right) $$

这种按位处理的方式有助于我们高效地处理查询。

算法步骤

1. 建立 $20$ 棵线段树（或二叉索引树 / 笛卡尔树），每棵树对应一个二进制位（即表格中的一列）。
2. 对于查询操作（求区间和）：
   • 对每个二进制位，统计该位在区间 $[l, r]$ 中 $1$ 的个数；
   • 将每个位的贡献乘以对应的 $2^j$ 后累加。
3. 对于异或操作（区间异或 $x$）：
   • 只对 $x$ 的二进制表示中为 $1$ 的那些位进行操作；
   • 对于这些位，将区间 $[l, r]$ 中所有 $b_{i,j}$ 取反（$0$ 变 $1$，$1$ 变 $0$）。
4. 上述两种操作都可以通过线段树的区间查询和区间翻转（懒标记）高效实现。

复杂度分析

• 每次操作需要对 $20$ 个二进制位分别处理；
• 每个二进制位的线段树操作时间复杂度为 $O(\log n)$；
• 总时间复杂度为 $O(m \cdot \log n \cdot 20)$，其中 $m$ 是操作次数。

代码说明

• 使用 $20$ 棵线段树，每棵树维护一个二进制位的区间和；
• 每棵树支持两种操作：
  • 区间查询：统计区间内 $1$ 的个数；
  • 区间翻转：将区间内所有 $0$ 变为 $1$，$1$ 变为 $0$；
• 对于异或操作，遍历 $x$ 的每一位，若该位为 $1$，则对应位的线段树执行区间翻转；
• 对于求和操作，遍历所有 $20$ 位，查询区间内 $1$ 的个数，乘以 $2^j$ 后累加。

//XOR on segment

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m, a[MAXN], tag[25][MAXN * 4], cnt[25][MAXN * 4], d[MAXN * 4];

inline int lc(int p) { return p << 1; } //left child

inline int rc(int p) { return p << 1 | 1; } //right child

inline int read() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline void write(register int x) {
    if (x == 0) putchar('0');
    else {
        register int st[33], tp = 0;
        while (st[++tp] = x % 10, x /= 10);
        while (putchar(st[tp] ^ 48), --tp);
    }
    putchar('\n');
}

void push_up(int p, int x) {
    cnt[x][p] = cnt[x][lc(p)] + cnt[x][rc(p)];
}

void move_tag(int p, int l, int r, int x) {
    cnt[x][p] = (r - l + 1) - cnt[x][p];
    tag[x][p] ^= 1;
}

void push_down(int p, int l, int r, int x) {
    if (tag[x][p] != 0) {
        int mid = (l + r) >> 1;
        move_tag(lc(p), l, mid, x);
        move_tag(rc(p), mid + 1, r, x);
        tag[x][p] = 0;
    }
}

void build_tree(int p, int l, int r, int x) { //建树
    if (l == r) {
        cnt[x][p] = (a[l] & d[x]) != 0;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(lc(p), l, mid, x);
    build_tree(rc(p), mid + 1, r, x);
    push_up(p, x);
}

int query(int p, int l, int r, int ql, int qr, int x) { //求和
    if (ql <= l && r <= qr) {
        return cnt[x][p];
    }
    push_down(p, l, r, x);
    int res = 0, mid = (l + r) >> 1;
    if (ql <= mid) {
        res += query(lc(p), l, mid, ql, qr, x);
    }
    if (qr > mid) {
        res += query(rc(p), mid + 1, r, ql, qr, x);
    }
    return res;
}

void update(int p, int l, int r, int ql, int qr, int x) { //反转
    if (ql <= l && r <= qr) {
        move_tag(p, l, r, x);
        return;
    }
    int mid = (l + r) >> 1;
    push_down(p, l, r, x);
    if (ql <= mid) {
        update(lc(p), l, mid, ql, qr, x);
    }
    if (qr > mid) {
        update(rc(p), mid + 1, r, ql, qr, x);
    }
    push_up(p, x);
}

void solve() {
    n = read();
    for (int i = 0; i < 20; ++i) { //初始化（一定要初始化）
        d[i] = (1 << i);
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    for (int i = 0; i < 20; ++i) {
        build_tree(1, 1, n, i);
    }
    m = read();
    while (m--) {
        int op = read();
        int l = read(), r = read();
        if (op == 1) {
            long long res = 0; //开ll
            for (int i = 0; i < 20; ++i) {
                res += 1LL * d[i] * query(1, 1, n, l, r, i);
            }
            cout << res << '\n';
        }
        if (op == 2) {
            int x = read();
            for (int i = 0; i < 20; ++i) {
                if (x & d[i]) update(1, 1, n, l, r, i);
            }
        }
    }
}

int main() {
    solve();
    return 0;
}