求2~m范围内所有素数。 常规方法：复杂度O(n*sqrt(n)) 枚举2~m之间的每个数k for(int i=2;i<=sqrt(k);++i){ if(k%i==0) return false; } return true;素数筛法：O(nlogn) vector<int>v; // 2~m 非素数的位置最终都置为0 v.resize(m+1,1); void func(vector<int>& v){ int n = v.size()-1; // 先把偶数的位置都置为0 最终特别增加处理2的情况 for(int i=...

RMQ RMQ(range min/max query)区间最值查询算法。经典场景：给定一个数组A[1...N]，有N个数字。查询区间[l,r]，求该区间的最大/最小值。常规方法是对[l,r]进行遍历，复杂度O(n)。当查询次数K巨大时，性能会很差。RMQ算法需要nlogn时间进行预处理，之后以O(1)时间响应查询。(当然还可以使用线段树) 原理 使用二维数组dp,dp[i][j]表示从第i位开始连续2^j个数中的最值。例如dp[2][1]就是第二个数开始连续两个数的最值(A[2],A[3]),dp[i][0]表示第i个数本身。求解dp[i][j]时，我们知道共2^j个数，必定是2的次幂，根据...

lowbit运算 lowbit(x) = x&(-x)取x的二进制表示最右边的1和它右边的所有0.结果一定是2的次幂。例如： 定义 树状数组C仍是一个数组，与前缀和数组sum类似，它是一个用来记录和的数组，只不过它存放的不是前i个整数之和，而是在i号位之前(含i号位)lowbit(i)个整数之和。C[i]的覆盖长度是lowbit(i),也可以理解成管辖范围。它是2的幂次，如1，2，4，8等。 两个操作getSum(x)返回前x个数之和A[1]+...+A[x]update(x,v)将第x个数加上v，即A[x]+=v 树状数组的应用 思路：若使用hash数组的解法，其中hash[x...