前言

比较常见的树链剖分题。

前置知识：线段树 + 树链剖分

这类维护区间位运算的题目往往采用：拆位线段树维护。

思路

笔者默认做题者会树链剖分，这里就简单讲讲拆位线段树。

考虑到区间异或和，影响答案的只有区间内的数二进制下的某几位是否为$1$，于是我们很自然的将问题分解为：

• 区间内的所有数中，二进制下第 $i$ 位为 $1$ 的数一共有多少个？

知道了这个我们就很容易得到最后的答案了。

很显然的一点，假设区间内第 $i$ 为 $1$ 的数一共有奇数个，那么这一位是可以贡献给最终答案的，答案就加上 $1 << i$ 。如果是偶数它的贡献会被异或消除为 $0$ ，对最终答案没有影响。

• 修改操作

我们实际上只需要单点修改某个位置上的线段树值即可。

于是就直接清空线段树上这个点的所有值，按照给出的数来进行按位分解后统计即可。

具体做法：

线段树中存储区间 $[L,R]$ 中第 $i$ 位为 $1$ 的数的个数，记作 $cnt[i]$

然后对于每一次查询，我们就开一个全局数组（用一次就得清空一次），按照线段树的传统做法，对于完全被包含的就将线段树中的值加入到这个数组中。传统线段树即可。

对于每次修改，找到 $pos$(修改的点) ，然后将当前点的对应的线段树的$cnt$ 数组清空，然后将给定的值转为二进制，暴力统计第 $i$ 位是否为 $1$ 即可。

代码实现可以看下面的 "$Code$" 部分，有注释。

时间复杂度：O($nlog^2n * 32$)(其实是跑不满的，效率还蛮高的)

$Code$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int start[MAXN],n,tot = 0,Q,now = 0;
int dep[MAXN],siz[MAXN],son[MAXN],fa[MAXN];
int dfn[MAXN],dfn_id[MAXN],tp[MAXN],val[MAXN],Ans[35];//Ans就是上文提到的全局数组

struct Edge {
    int to,next;
} edge[MAXN * 2];

struct SegmentTree {
    int l,r;
    int cnt[33];
} T[MAXN * 4];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void add(int from,int to)
{
    tot ++;
    edge[tot].to = to;
    edge[tot].next = start[from];
    start[from] = tot;
    return ;
}

int DFS1(int x,int from)//树链剖分DFS1
{
    siz[x] = 1 , dep[x] = dep[from] + 1;
    son[x] = 0 , fa[x] = from;
    for(int i = start[x] ; i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(to == from) continue;
        int v = DFS1(to,x);
        if(v > siz[son[x]]) son[x] = to;
        siz[x] += v;
    }
    return siz[x];
}

void DFS2(int x,int top)//树链剖分DFS2
{
    tp[x] = top , dfn[x] = ++now , dfn_id[now] = x;
    if(son[x]) DFS2(son[x],top);
    for(int i = start[x] ; i ; i = edge[i].next)
    {
        int to = edge[i].to;
        if(to == fa[x] || to == son[x]) continue;
        DFS2(to, to);
    }
    return ;
}

void build(int x,int l,int r)
{
    T[x].l = l , T[x].r = r;
    if(l == r)
    {
        int D = val[dfn_id[l]],len = 0;
        while(D)//进行二进制分解
        {
            T[x].cnt[++len] += (D & 1);
            D >>= 1;
        }
        return ;
    }
    int mid = (l + r) >> 1;
    build(x << 1 , l , mid);
    build(x << 1 | 1 , mid + 1 , r);
    for(int i = 1 ; i <= 32 ; i ++)//直接暴力的将两个儿子的值给获取掉
        T[x].cnt[i] = T[x << 1].cnt[i] + T[x << 1 | 1].cnt[i];
    return ;
}

void change(int x,int pos,int k)
{
    if(T[x].l == dfn[pos] && T[x].r == dfn[pos])
    {
        int D = val[pos],len = 0;
        while(D)//常数优化，因为直接全部清空太浪费了，有些本来就没被访问
        {
            T[x].cnt[++len] -= (D & 1);
            D >>= 1;
        }
        D = k;
        len = 0;
        while(D)
        {
            T[x].cnt[++len] += (D & 1);
            D >>= 1;
        }
        val[pos] = k;//上面的常数优化需要知道当前点的被修改前的值为多少，所以要保存
        return ;
    }
    int mid = (T[x].l + T[x].r) >> 1;
    if(dfn[pos] <= mid) change(x << 1 , pos , k);
    else change(x << 1 | 1 , pos , k);
    for(int i = 1 ; i <= 32 ; i ++)
        T[x].cnt[i] = T[x << 1].cnt[i] + T[x << 1 | 1].cnt[i];
    return ;
}

void Get(int x,int l,int r)
{
    if(T[x].l >= l && T[x].r <= r)
    {
        for(int i = 1 ; i <= 32 ; i ++) 
        Ans[i] += T[x].cnt[i];//上文提到的将线段树中的值暴力加入答案中
        return ;
    }
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) Get(x << 1 , l , r);
    if(r  > mid) Get(x << 1 | 1 , l , r);
    return ;
}

void GetAns(int x,int y)//树链剖分模板
{
    while(tp[x] != tp[y])
    {
        if(dep[tp[x]] < dep[tp[y]]) swap(x,y);
        Get(1 , dfn[tp[x]] , dfn[x]);
        x = fa[tp[x]];
    }
    if(dfn[x] < dfn[y]) Get( 1 , dfn[x] , dfn[y]);
    else Get(1 , dfn[y] , dfn[x]);
    return ;
}

int main()
{
    n = read() , Q = read();
    for(int i = 1 ; i <= n ; i ++) val[i] = read();
    for(int i = 1 ; i <= n - 1 ; i ++)
    {
        int u = read() , v = read();
        add(u,v); add(v,u);
    }
    DFS1(1,0);
    DFS2(1,1);
    build(1 , 1 , n);
    while(Q -- )
    {
        int op = read() , l = read() , r = read();
        if(op == 1) change( 1 , l , r);
        else 
        {
            memset(Ans,0,sizeof(Ans));//每次用都要清空
            GetAns( l , r );
            int sum = 0;
            for(int j = 1 ; j <= 32 ; j ++)
            if(Ans[j] & 1) sum += (1 << (j - 1));//是奇数的话就对答案有贡献
            //注意这里要减一，因为分解的时候第1位相当于2的0次方
            printf("%d\n",sum);
        }
    }
    return 0;
}