看到的大佬帮忙看看吧QAQ求求了

写了两个版本，样例都不过（主要是输出都错在同样的地方）

递归版：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 20000010;

int n, m, idx, w[N], lastans;
struct Tree
{
	int s[2]; // 表示左右儿子的 idx 
	int add, sum, size;
	
	#define ls tr[u].s[0]
	#define rs tr[u].s[1]
}tr[N];

void pushup(int u)
{
	tr[u].size = tr[ls].size + tr[rs].size + 1;
	tr[u].sum += tr[ls].sum + tr[rs].sum;
}

void pushdown(int u)
{
	if (tr[u].add)
	{
		tr[ls].add += tr[u].add;
		tr[rs].add += tr[u].add;
		tr[ls].sum += tr[ls].size * tr[u].add;
		tr[rs].sum += tr[rs].size * tr[u].add;
		tr[u].add = 0;
	}
}

void insert(int u, int x, int v)
{
	if (!x)
	{
		tr[u].sum = v, tr[u].size = 1;
		return;
	}
	
	int az = x & 1;
	if (!tr[u].s[az]) tr[u].s[az] = ++ idx;
	insert(tr[u].s[az], x >> 1, v);
	pushup(u);
}

void build(int n)
{
	for (int i = 1; i <= n; i ++ )
		insert(0, i, w[i]);
}

void modify(int u, int c, int v)
{
	if (!c)
	{
		tr[u].add += v, tr[u].sum += tr[u].size * v;
		return;
	}
	
	pushdown(u);
	int az = c & 1;
	modify(tr[u].s[az], c >> 1, v);
	pushup(u);
}

int query(int u, int c)
{
	if (!c) return tr[u].sum;
	
	pushdown(u);
	int az = c & 1;
	return query(tr[u].s[az], c >> 1);
}

int main()
{
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &w[i]);
		
	build(n);
	
	while (m -- )
	{
		int op, x, y, v;
		scanf("%d", &op);
		op = (op + lastans) % 2 + 1;
		
		if (op == 1)
		{
			scanf("%d%d%d", &x, &y, &v);
			modify(0, y % (1 << x), v);
		}
		
		else
		{
			scanf("%d%d", &x, &y);
			printf("%d\n", lastans = query(0, y % (1 << x)));
		}
	}
	
	return 0;
}

迭代版

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m, idx, w[N], lastans;
struct Tree
{
	int s[2]; // 表示左右儿子的 idx 
	int add, sum, size;
	
	#define ls tr[u].s[0]
	#define rs tr[u].s[1]
}tr[N];

void pushup(int u)
{
	tr[u].size = tr[ls].size + tr[rs].size + 1;
	tr[u].sum += tr[ls].sum + tr[rs].sum;
}

void pushdown(int u)
{
	if (tr[u].add)
	{
		tr[ls].add += tr[u].add;
		tr[rs].add += tr[u].add;
		tr[ls].sum += tr[ls].size * tr[u].add;
		tr[rs].sum += tr[rs].size * tr[u].add;
		tr[u].add = 0;
	}
}

void insert(int x)
{
	int p = 0, u = x;
	while (x)
	{
		int v = x & 1;
		if (!tr[p].s[v]) tr[p].s[v] = ++ idx;
		p = tr[p].s[v]; 
		x >>= 1;
	}
	
	tr[p].sum = w[u], tr[p].size = 1;
	pushup(p);
}

void build(int n)
{
	for (int i = 1; i <= n; i ++ )
		insert(i);
}

void modify(int c, int v) // 将二进制后缀为 c 的子树增加 v 
{
	int p = 0;
	while (c)
	{
		pushdown(p);
		int v = c & 1;
		if (!tr[p].s[v]) return;
		p = tr[p].s[v];
		c >>= 1;
	}
	
	// 现在需要将 p 的子树增加 v 
	tr[p].add += v, tr[p].sum += tr[p].size * v;
	pushup(p);
}

int query(int c) // 求二进制后缀为 c 的子树和 
{
	int p = 0;
	while (c)
	{
		pushdown(p);
		int v = c & 1;
		if (!tr[p].s[v]) return 0;
		p = tr[p].s[v];
		c >>= 1;
	}
	
	return tr[p].sum;
}

int main()
{
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &w[i]);
		
	build(n);
	
	while (m -- )
	{
		int op, x, y, v;
		scanf("%d", &op);
		op = (op + lastans) % 2 + 1;
		
		if (op == 1)
		{
			scanf("%d%d%d", &x, &y, &v);
			modify(y % (1 << x), v);
		}
		
		else
		{
			scanf("%d%d", &x, &y);
			printf("%d\n", lastans = query(y % (1 << x)));
		}
	}
	
	return 0;
}