树形dp进阶__位运算与树形dp

· · 个人记录

回到根源

首先我们要认识的是，所有的数据结构的目的都是为了加速查询，区间查询通过前缀和来实现，也就是说符合前缀和性质的所有运算都可以使用树状数组来优化查询，包括位运算

P6225

就按照这题为例，如图，我们可以发现当从x出发的时候，以y为终点，就可以发现他出现的次数每个元素为y-x+1次 所以我们需要分开来看一个数是否为偶数，需要使用两棵树来分别存储
然后在修改的时候继续判起点和终点，如果起点和终点一偶一奇，那么所有元素都被抵消，变成0
如果起点和终点同奇或者同偶，那么需要分类
如果同奇，则只有i为奇数是答案才会有效果
如果同偶，则只有i为偶数是答案才会有效果
然后两棵树分开来算就可以了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+7;
int a[maxn];
int n,q;
struct Node {
    int c[maxn];
    int lowbit(int x) {
        return (x&(-x));
    }
    int query(int x) {
        int ans=0;
        while(x) {
            ans^=c[x];
            x-=lowbit(x);
        }
        return ans;
    }
    void modify(int x,int v) {
        while(x<=n) {
            c[x]^=v;
            x+=lowbit(x);
        }
        return ;
    }
} tr1,tr2;
signed main() {
    cin>>n>>q;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        if(i&1) {
            tr1.modify(i,a[i]);
        } else {
            tr2.modify(i,a[i]);
        }
    }
    while(q--) {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1) {
            if(x&1) {
                tr1.modify(x,a[x]^y);
            } else {
                tr2.modify(x,a[x]^y);
            }
            a[x]=y;
        } else {
            if((x&1)==(y&1)) {
                if(x&1) {
                    cout<<(tr1.query(y)^tr1.query(x-1))<<'\n';
                } else {
                    cout<<(tr2.query(y)^tr2.query(x-1))<<'\n';
                }
            } else {
                cout<<0<<'\n';
            }
        }
    }
    return 0;
}