题解||线段树

线段树我爱你、、、

线段树模版，就是查询区间异或值。

冷知识：用树状数组做的似乎都能用线段树做（？）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4000005;
vector<int> a(N);
class segment_tree{
    private:
        struct node{
            int lazy=0,data;
        }tree[N];
        int left_child(int now){//取左孩子，返回的是索引
            return 2*now;
        }int right_child(int now){//取右孩子
            return 2*now+1;
        }
    public:
        void build(int now,int l,int r){//递归建树
            tree[now].lazy=0;//懒标记的初始化，后面会讲
            if(l==r){//叶子节点
                tree[now].data=a[l];
                return ;
            }int mid=l+(r-l)/2;
            build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
            tree[now].data=tree[left_child(now)].data^tree[right_child(now)].data;//赋值该节点为他的左右孩子节点值之和。
        }
        int query_XOR(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
            if(ql>r or qr<l)return 0;
            if(ql<=l and qr>=r)return tree[now].data;
            int mid=l+(r-l)/2;
            return query_XOR(left_child(now),l,mid,ql,qr)^query_XOR(right_child(now),mid+1,r,ql,qr);
        }
        void update(int now,int l,int r,int idx,int val){//单点更新
            if(l==r){
                tree[now].data=val;
                return ;
            }int mid=l+(r-l)/2;
            if(idx<=mid){
                update(left_child(now),l,mid,idx,val);
            }else{
                update(right_child(now),mid+1,r,idx,val);
            }tree[now].data=tree[left_child(now)].data^tree[right_child(now)].data;
        }
};
signed main(){
    segment_tree tree;
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }tree.build(1,1,n);
    while(m--){
        int op;
        cin >> op;
        if(op==1){
            int x,y;
            cin >> x >> y;
            tree.update(1,1,n,x,(tree.query_XOR(1,1,n,x,x)^y));
        }else{
            int x,y;
            cin >> x >> y;
            cout << tree.query_XOR(1,1,n,x,y) << "\n";
        }
    }
    return 0;
}

时间复杂度：$\mathcal{O}(n+q\log n)$
空间复杂度：$\mathcal{O}(n)$