NOJ——1669xor的难题（详细的树状数组扩展

[1669] xor的难题
时间限制: 1000 ms　内存限制: 65535 K
问题描述
最近Alex学长有个问题被困扰了很久，就是有同学给他n个数，然后给你m个查询，然后每个查询给你l和r(左下标和右下标)，然后问你每个查询l到r之间数字的xor值。(al ^ ... ^ ar)。
输入
输入t组数据，下一行输入n (1 <=n <=10^5)和m (1 <=m <= 10^4)，第三行输入n个数字ai(0 <=ai <= 10^8)，第四行输入m个询问l和r(1 <=l <=r <= n)。
输出
每个询问输出区间xor值的答案。
样例输入
```
1

3 2

0 1 2

1 2

3 3
```
样例输出
```
1

2
```
呃呃呃树状数组果然效果出众，从暴力800+ms变成了200+ms，学长深不可测，再感谢下阙神的指导，不然还不知道如何将树状数组扩展成异或形式求和。

主要问题就是这个树状数组如何构建：

首先建立一个一维（二维暂时没做到）的数组，作为树状数组的主体，然后运用add函数进行构建树状数组（每一个端点值附着在上面），然后用另一个getsum函数进行求和Sum[1~index]。当然一个区间和 Sum[L,R]=Sum[r]-Sum[l-1]。至此，一个树状数组普通求和就可以顺利进行了，那么异或求和例如an^an+1^......^am如何求和？通过阙神指导和之前的记忆，先把add和getsum中所有关于val（下标+号千万别动）的加号改为^号，然后最后答案的Sum[r]-Sum[l-1]中减号改为^号。

代码：

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

const int n = 100009;

int tree[n];

void add(int k, int val)

{

    while (k <= n)

    {

        tree[k] ^= val; //加号改^号

        k += k & -k; //这里是下标的操作，不能动

    }

}

int getsum(int k)

{

    int sum = 0;

    while (k)

    {

        sum ^= tree[k]; //加号改^号

        k -= k & -k; /

    }

    return sum;

}

int main(void)

{

    int i, j, s, m, l, r, t, g;

    scanf("%d", &t);

    while (t--)

    {

        memset(tree, 0, sizeof(tree));

        scanf("%d%d", &g, &m);

        for (i = 1; i <= g; i++)

        {

            scanf("%d", &s);

            add(i, s); //枝点更新（附着）

        }

        for (i = 0; i < m; i++)

        {

            scanf("%d%d", &l, &r);

            printf("%d\n", getsum(r)^getsum(l - 1)); //减号改^号

        }

    }

    return 0;

}

巴特西

NOJ——1669xor的难题（详细的树状数组扩展—异或求和）

[1669] xor的难题

最新文章

热门文章