前缀和数组

求数组[L,R]上的和

方法1：直接累加[L,R]上的和

int rangeSum(int* a,int L, int R)
{
    int sum = 0;
    //求数组[L,R]范围上的和
    for (int i = L; i <= R; i++)
    {
        sum += a[i];
    }
    return sum;
}

为了更快,可以多次查找一个区间的累加和:可以直接求出前缀和数组

前缀和数组表达式:presum[i] = presum[i-1] + arr[i] 即前缀和数组下标为i位置的值,是其前一项i-1位置的值+数组i位置的值 且:presum[0] = arr[0],从i = 1的位置开始计算

#include<iostream>
using namespace std;
//求前缀和数组
int* Range(int* a, int n)
{
    int* preSum = new int[n] {0};
    preSum[0] = a[0];//前缀和数组的第一个值就是数组a[0]的值
    for (int i = 1; i < n; i++)
    {
        preSum[i] = preSum[i - 1] + a[i];
    }
    return preSum;
}
//求数组arr [L,R]范围上的和
int rangeSum(int*preSum,int L, int R)
{
    //如果L == 0返回:preSum[R]
    //否则返回:  preSum[R] - preSum[L-1]
    return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
}
int main()
{
    int arr[] = { 1,2,3,4,5,6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int* preSum = Range(arr, n);
    cout << rangeSum(preSum, 0,0) << endl;
}

位图

一个整数:可以表示32位,可以根据其每一位二进制情况判断0-31的数是否出现

一个长度为32的数组,可以表示0-1023的数是否出现

以整数的二进制位为0还是1表示:如:下标为0的二进制第一位表示表示0的是否出现,第32位表示31是否出现

下标为1的二进制第一位表示32是否出现....

位图的好处:压缩空间

基本结构

class BitMap
{
 private:
    long* bits;//指向一个数组  
};

构造函数

构造函数-开辟空间

数组元素类型是long ==> 一个元素可以表示64个数是否存在
每64个数就需要一个空间,要开的空间数:(max+64)/64

• 注意:要把数组的元素初始化为0

BitMap(int max = 0)
{
    //(max + 64) >> 6  相当于：(max+64)/64
    //表示:0-63 ,max = 63 需要(max+64)/64 = 1个空间
    bits = new long[(max + 64) >> 6]{ 0 };//注意数组所有元素要初始化为0,否则是随机数
}

添加

添加的含义:加入某个数 ->即将对应数组某个下标的元素的某个二进制位置1

long类型元素,有64位可以表示64个数是否存在

->num/64代表num属于下标为几的元素,num%64代表在该元素的哪个比特位

注意:num/64 == num%63

步骤:1.得到在数组的所在元素下标 2. 2.在该元素的对应比特位置1 ->或上1

void add(int num)
{
    //1.得到在哪个元素 2.在该元素的对应比特位置1 ->或上1
    bits[num >> 6] |= (1L << (num & 63));
}

删除

步骤:1.得到在数组的所在元素下标 2.在该元素的对应比特位置0 ->与上0

//删除同理 
void del(int num)
{
    //1.得到在哪个元素 2.在该元素的对应比特位置0  ->与上0
    bits[num >> 6] &= ~(1L << (num & 63));
}

查找

步骤:1.得到在数组的所在元素下标 2.得到该元素的对应比特位是0还是1 ->和1在该比特位相与

//查询是否在这个集合
bool search(int num)
{
    //1.得到在哪个元素 2.得到该元素的对应比特位是0还是1 ->和1在该比特位相与
    //注意操作符的优先级顺序
    return( bits[num >> 6] & (1L << (num & 63))) != 0;
}

坑点:

左移的使用,要使用1L ,不能使用1,因为1默认是整形,只有32位, 而1L是long类型,有64位

如果用1的话,如果左移的长度大于31就会发生错误!

Bitmap.h

#pragma once
#include<iostream>
using namespace std;

class BitMap
{
public:
    //构造函数-开辟空间
    //数组元素类型是long ->一个元素可以表示64个数是否存在
    //每64个数就需要一个空间,要开的空间数:(max+64)/64
    BitMap(int max = 0)
    {
        //(max + 64) >> 6  相当于：(max+64)/64
        //表示:0-63 ,max = 63 需要(max+64)/64 = 1个空间
        bits = new long[(max + 64) >> 6]{ 0 };//注意数组所有元素要初始化为0,否则是随机数
    }
    //加入某个数 ->将对应数组某个下标的元素的某个二进制位置1
    //long类型可以表示64个数是否存在 
    //num/64代表num属于下标为几的元素,num%64代表在该元素的哪个比特位
    //num/64 == num%63
    void add(int num)
    {
        //1.得到在哪个元素 2.在该元素的对应比特位置1 ->或上1
        bits[num >> 6] |= (1L << (num & 63));
    }
    //删除同理 
    void del(int num)
    {
        //1.得到在哪个元素 2.在该元素的对应比特位置0  ->与上0
        bits[num >> 6] &= ~(1L << (num & 63));
    }
    //查询是否在这个集合
    bool search(int num)
    {
        //1.得到在哪个元素 2.得到该元素的对应比特位是0还是1 ->和1在该比特位相与
        //注意操作符的优先级顺序
        return( bits[num >> 6] & (1L << (num & 63))) != 0;
    }

private:
    long* bits;//指向一个数组
};

位运算小技巧

(x & 1) == 1 等价---> (x % 2 == 1)
(x & 1) == 0 等价---> (x % 2 == 0)
x / 2 等价---> x >> 1
x &= (x - 1) --> 将整数n的二进制表示中的最后一个1置0
x & -x --> 得到最低位的1
x & ~x --> 得到0