原题链接

这题一般的做法是递归的普通线段树，但是我可以察觉到，这道题明显操作树是一个完全二叉树，而且更新完全发生在叶子节点上，我们完全可以从叶子节点迭代而上。

纯自主想出来的，写完了之后查了一下，貌似这玩意就是 zkw 线段树。可惜生不逢时，要是早几年就是用我名字命名了。

但是好像和 zkw 也不太一样，毕竟很少有正常人会用多维 vector 存线段树。

貌似全网没有类似做法。

自己看代码吧，很好懂：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
using namespace std;

#define int long long
// #define cout cout << ">>>"

const int maxn = 2e5;
vector<int> tree[maxn];

int n, m;
int a[maxn];

int pow2(int x) {
	int ans = 1;
	while (x--) {
		ans *= 2;
	}
	return ans;
}

int ls(int id) {
	return (id << 1) - 1;
}
int rs(int id) {
	return id << 1;
}
int getfa(int id) {
	return (id + 1) / 2;
}
void pushup(int dep, int x) {
	if ((n - dep) % 2 == 0) {
		tree[dep][x] = tree[dep + 1][ls(x)] | tree[dep + 1][rs(x)];
	} else {
		tree[dep][x] = tree[dep + 1][ls(x)] ^ tree[dep + 1][rs(x)];
	}
}
void build() {
	int dep = n;
	while (dep >= 1) {
		for (int i = 1; i <= pow2(dep - 1); i++) {
			pushup(dep, i);
		}
		dep--;
	}
}
void update(int p, int b) {
	tree[n + 1][p] = b;
	int dep = n;
	int cur = p;
	while (dep >= 1) {
		int fa = getfa(cur);
		pushup(dep, fa);
		cur = fa;
		dep--;
	}
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= pow2(n); i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n + 1; i++) {
		tree[i].resize(pow2(i) + 10);
	}
	for (int i = 1; i <= pow2(n); i++) {    // 直接去叶子节点打数值
		tree[n + 1][i] = a[i];
	}
	build();                                // 叶子节点打完数值后，直接从叶子节点开始迭代而上更新父亲
	while (m--) {
		int p, b;
		cin >> p >> b;
		update(p, b);
		cout << tree[1][1] << endl;
	}
	return 0;
}