首页 > 其他分享 >前缀异或和

前缀异或和

时间:2024-04-01 14:55:41浏览次数:22  
标签:preXor queriesSize 前缀 int 异或 ans

异或是可以用前缀和来维护的,因为异或有一个重要的性质x ^ x = 0

设preXor[i] = a[0] ^ a[1] ^ a[2] ^ a[3] ^ a[4] ^ ..... ^ a[i]

那么给定一个[l, r]范围的区间求a[l,r]的异或和,我们就可以利用前缀异或和来求解

preXor(l, r) = preXor(0, r) ^ preXor(0, l - 1) = preXor[r] ^ preXor[l - 1] = (a[0] ^ a[1] ^ a[2] ^ a[l - 1] ^ a[l] ^ a[l + 1]  ^ .......... ^ a[r]) ^ (a[0] ^ a[1] ^ a[2] ^ .......... ^ a[l - 1]) = a[l] ^ a[l + 1] ^ ........ ^ a[r]

1310.子数组异或查询

解题思路

  1. 利用异或的性质,构建一个异或前缀和数组,来实现快速查询区间的异或和

代码实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* xorQueries(int* arr, int arrSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int preXor[30005] = {0};

    for (int i = 0; i < arrSize; i ++) {
        preXor[i + 1] = arr[i] ^ preXor[i];
    }

    int* ans = (int*)malloc(sizeof(int) * queriesSize);

    for (int i = 0; i < queriesSize; i ++) {
        ans[i] = preXor[queries[i][0]] ^ preXor[queries[i][1] + 1];//前缀和下标从1开始数所以要加一
    }

    *returnSize = queriesSize;

    return ans;
}

 

标签:preXor,queriesSize,前缀,int,异或,ans
From: https://www.cnblogs.com/lwj1239/p/18108336

相关文章

  • Hashmap源码什么要对hashcode做一次高16位异或低16位的操作
    翻译一下就是:计算键的hashCode()方法,并将其高几位通过异或操作传播到低位。因为哈希表使用二的幂次方进行掩码操作,那些仅在当前掩码位之上不同的哈希集将会一直发生冲突。(已知的例子包括在小表中保存连续整数的Float键集。)因此,我们应用了一种变换来将高位的影响向下传播。在速度......
  • (67)动态口令 (68)解码异或后的数组
    文章目录每日一言题目(67)动态口令解题思路代码题目(68)解码异或后的数组解题思路代码结语每日一言我们并不清楚,人类为何降生到这个世界;但我们可以试着去发现,这是一个什么样的世界。题目(67)动态口令题目链接:动态口令某公司门禁密码使用动态口令技术。初始密码......
  • 蓝桥杯 2022 省A 选数异或
    一种比较无脑暴力点的方法,时间复杂度是(n²+m)。(注意==的优先级比^高,记得加括号(a[i]^a[j])==x)#include<iostream>#include<vector>#include<bits/stdc++.h>//包含一些C++标准库中未包含的特定实现的函数的头文件usingnamespacestd;intmain(){intn,......
  • 位运算-异或(^)
    1基本概念1.1符号异或是一种二进制的位运算,符号以XOR或^表示。1.2运算规则相同为0,不同为1,即(可以看做二进制下的不进位加法)1^1=00^0=01^0=11.3运算性质交换律:A^B=B^A结合律:(A^B)^C=A^(B^C)自反性:A^B^B=A(由结......
  • Leetcode 【930. 和相同的二元子数组】【统计「优美子数组」】【974. 和可被 K 整除的
    这道题目是经典的求子数组之和=goal的个数,用map维护。但是笔者在实现的过程中发现0的情况不是很好出来,问题在于mp[sum]和sum+=num的代码语句存在位置问题。后来看了下代码还是自己没有考虑清楚。这种类型的题目就是要想清楚你的做法,以及边界条件。classSolution{public:......
  • Nginx配置静态代理/静态资源映射时root与alias的区别,带前缀映射用alias
    场景Nginx搭建静态资源映射实现远程访问服务器上的图片资源:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/117283572以上在配置静态资源映射时使用的如下配置     location/{           root  D:/pic_old/;           try_......
  • 前缀和与差分数组
    目录一维前缀和二维前缀和差分数组差分数组反推出原始数组差分数组模板前缀和应用场景:原始数组不会被修改的情况下,频繁查询某个区间的累加和。eg:计算数组下标2到5的数组和,原本用for循环,有了前缀和直接用5的前缀和减去2的前缀和得到答案,可以将O(n)的复杂度降为O(1)一维前缀和......
  • 前缀和算法讲解(二)
    首先,大家看一下一维的前缀和:https://blog.csdn.net/hjyowl/article/details/136580832?spm=1001.2014.3001.5502今天,我们讲解一下二维的前缀和.先看题:输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下......
  • 异或绕过及其原理
    异或的原理总的来说,异或就是两个字符的二进制进行异或比如:a=01010101;//假设其为二进制b=10101010;c=a^b;//进行异或c=11111111;总的来说就是两个字符二进制一个为0,另一个为1时,异或结果为1只要不同就为1,相同就为0。为什么上面的异或和在CTF题中看到的不一样......
  • 蓝桥杯算法基础(29)字符串匹配(RabinKarp)(KMP)(前缀树,字典树,trie,后缀数组,高度数组)
     RabinKarpRabinKarpS:ABABABm个P:ABBn个1.朴素算法,挨个匹配2.哈希法hash->滚动哈希c0*31^2+c1*31^1+c2类似于进制的求法求hash值(c0*31+c1)*31+c2hash(p)=o(n)hash(s)=o(m*n)privatestaticvoidmatch(Stringp,Strings){longhash_p=hash(p);......