rt，一颗普通的拆位线段树

#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
#include <string.h>
#include <queue>
#include <stdio.h>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N]; 
struct node
{
	int l, r;
	int lazy;
	int cnt[114];
}tr[N << 2];
void push_up(int u)
{
	for(int i = 0; i <= 20; i++)
	{
		int lc = tr[u << 1].cnt[i];
		int rc = tr[u << 1 | 1].cnt[i];
		tr[u].cnt[i] = lc + rc;
	}
	return ;
}
void build(int u, int l, int r)
{
	tr[u].l = l, tr[u].r = r;
	if(l == r)
	{
		for(int i = 0; i <= 20; i++)
		{
			if((a[l] >> i) & 1) tr[u].cnt[i] = 1;
		}
		return ;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	push_up(u);
}
void push_down(int u, int l, int r)
{
	if(!tr[u].lazy) return ;
	int mid = (l + r) >> 1;
	for(int i = 0; i <= 20; i++)
	{
		if((tr[u].lazy >> i) & 1)
		{
			tr[u << 1].cnt[i] = (mid - l + 1) - tr[u << 1].cnt[i];
			tr[u << 1 | 1].cnt[i] = (r - mid) - tr[u << 1 | 1].cnt[i];
		}
	}
	tr[u << 1].lazy ^= tr[u].lazy;
	tr[u << 1 | 1].lazy ^= tr[u].lazy;
	tr[u].lazy = 0;
	return ;
}
void update(int u, int l, int r, int x)
{
	if(l <= tr[u].l && tr[u].r <= r)
	{
		for(int i = 0; i <= 20; i++)
		{
			if((x >> i) & 1) tr[u].cnt[i] = (r - l + 1) - tr[u].cnt[i];
		}
		tr[u].lazy ^= x;
		return ;
	}
	int mid = (tr[u].l + tr[u].r) >> 1;
	push_down(u, tr[u].l, tr[u].r);
	if(l <= mid) update(u << 1, l, r, x);
	if(mid < r) update(u << 1 | 1, l, r, x);
	push_up(u);
}
int query(int u, int l, int r)
{
	if(l <= tr[u].l && tr[u].r <= r)
	{
		int num = 0, po = 1;
		for(int i = 0; i <= 20; i++)
		{
			num += tr[u].cnt[i] * po;
			po <<= 1;
		}
		return num;
	}
	int mid = (tr[u].l + tr[u].r) >> 1;
	int ans = 0;
	push_down(u, l, r);
	if(l <= mid) ans += query(u << 1, l, r);
	if(mid < r) ans += query(u << 1 | 1, l, r);
	return ans;
}
int m;
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	build(1, 1, n);
	cin >> m;
	while(m--)
	{
		int opt, l, r;
		scanf("%lld%lld%lld", &opt, &l, &r);
		if(opt == 1)
		{
			printf("%lld\n", query(1, l, r));
		}
		if(opt == 2)
		{
			int x;
			scanf("%lld", &x);
			update(1, l, r, x);
		}
	}
	return 0;
}