这个题目属于线段树的点更新区间查询，而且查的是整个区间，其实不用写query（）函数，只需要输出根节点保存的值就可以了。
题意：
输入n,m表示有2^n个数和m个更新，每次更新只把p位置的值改成b，然后输出整个序列运算后的值，而这个运算就比较复杂了， 最下面一层两个数字之间或运算得到原来数目一半的数字，然后两个之间异或运算，得到一半，再或再异或………………，一直到得到一个数字，这个数字就是要求的结果。
思路：
如果只是一种运算，这就是简单的线段树点更新，区间查询。而现在，我们要确定什么时候用or 什么时候用xor， 想想看，最下面一层是用or， 总共有n层，因为or和xor是交替进行的，我们就可以用n确定每层的运算，然后在建树和更新的时候分情况讨论。
代码如下：
#include <stdio.h> #include <string.h> const int maxn = (1<<17) + 5; struct node { int l, r; int x; }tree[maxn<<2]; int arr[maxn]; void build(int l, int r, int o, int d) { tree[o].l = l; tree[o].r = r; if (l == r) { tree[o].x = arr[l]; return ; } int mid = (l + r) >> 1; build(l, mid, o<<1, -d); build(mid+1, r, o<<1|1, -d); if (d == 1) tree[o].x = tree[o<<1].x^tree[o<<1|1].x; else tree[o].x = tree[o<<1].x|tree[o<<1|1].x; } int query(int l, int r, int o) { if (tree[o].l == l && tree[o].r == r) return tree[o].x; int mid = (tree[o].l + tree[o].r) >> 1; if (r <= mid) return query(l, r, o<<1); else if (l > mid) return query(l, r, o<<1|1); else return query(l, mid, o<<1)^query(mid+1, r, o<<1|1); } void update(int x, int v, int o, int d) { if (tree[o].l == tree[o].r && tree[o].l == x) { tree[o].x = v; return; } int mid = (tree[o].l + tree[o].r) >> 1; if (x <= mid) update(x, v, o<<1, -d); else update(x, v, o<<1|1, -d); if (d == 1) tree[o].x = tree[o<<1].x^tree[o<<1|1].x; else tree[o].x = tree[o<<1].x|tree[o<<1|1].x; } int main() { int n, m; int p, b, d; while (scanf("%d %d", &n, &m) != EOF) { int num = 1<<n; for (int i = 1; i <= num; i++) scanf("%d", &arr[i]); if (n&1) d = -1; else d = 1; build(1, num, 1, d); while (m--) { scanf("%d %d", &p, &b); update(p, b, 1, d); printf("%d\n", query(1, num, 1)); } } return 0; }
