算法笔记（2）—— 数据预处理算法：前缀和算法、差分算法

发布于：2023-01-21 ⋅ 阅读:(448) ⋅ 点赞:(0)

        平时对数据的处理是不可避免的，从数据中查询信息和修改信息也是十分常规的操作，但对于海量的数据而言，这些操作会消耗大量时间进行一些不必要的重复操作，那有没有什么方法可以提速呢？有！那就是通过数据预处理的方法：前缀和算法和差分算法！

【本文会用 Python 和 C/C++ 语言实现前缀和算法及差分算法】

一、前缀和算法

算法介绍

        前缀和是一种对已知数据的预处理方法，目的是为了快速查询数据中的某个值的大小或某部分值的和，前缀和是指序列前面所有项的和

【预处理时间复杂度】与被处理数据的维数有关

【查询时间复杂度】O(1)

问题引入

        假设现在有一段长为 n 的序列，现在要求其索引为 left 和索引为 right 的值之间所有项的和，我们可以用循环进行遍历求和，如果要求 m 个这样的区间和的值，每次循环的时间复杂度为 O(n)，而要求 m 次，那么总的时间复杂度就是 O(nm)，显然在求和的过程中序列有部分被重复遍历了 m 次，这是不必要的，如何省去这段重复过程从而加快求和的速度呢？

一维前缀和

【预处理时间复杂度】O(n)

【空间复杂度】O(n)

【总时间复杂度】O(n + m)【m为查询次数】

一维前缀和处理就是将序列中的每一项的值重新更改为其与其前面每一项的和（如下）

//处理前
1  2  3  4  5  6  7 

//处理后
1  3  6 10 15 21 28

查询区间数据之和时，只需求出前缀和序列的数据端点之差，即索引为 left_index 和索引为 right_index 的值之间所有值的和 sum = new[right_index] - new[left_index-1]，其中 new 为处理后的序列，特别的，当 left_index = 0，sum = new[right_index] 

例如上述序列，求索引为 1 的值（2）到索引为 5 的值（6）之间所有数据的和，对于处理后的前缀和数组，这一值为 new[5]-new[1-1] = 21-1 = 20，原理如下

new[5]   = old[0] + old[1] + old[2] + old[3] + old[4] + old[5] = 21
new[1-1] = old[0]                                              = 1
sum=new[5]-new[0] = old[1] + old[2] + old[3] + old[4] + old[5] = 20

【图解算法】

一维前缀和

【数学表达式】

定义式

\small new[i]=\sum\limits_{k=0}\limits^iold[k],i\geqslant 0

在定义式中， new[i] 表示新数组索引为 k 的元素的值，old[k] 代表原数组索引为 k 的值

递推式

\small new[i]=new[i-1]+old[i],i\geqslant 1

在递推式中，new[i] 表示新数组索引为 i 的元素的值，old[i] 代表原数组索引为 i 的值，特别的，当 i=0 时，new[i] = old[i]

【算法实现】

Python实现

class PartialSum:#一维前缀和类
    def __init__(self, lis:list):#构造方法
        #lis：待处理的列表
        self.list = lis#前缀和列表
        self.length = len(lis)#前缀和列表长度
        self.__pretreatment()#调用预处理方法
    
    def __pretreatment(self):#预处理方法
        for i in range(1,self.length):
            self.list[i] += self.list[i-1]#递推式
    
    def query(self, left:int, right:int):#查询方法
        #left:左索引 right:右索引
        return self.list[right]-self.list[left-1]*(left>0)

C/C++实现

class PartialSum//一维前缀和类
{
	private:
		
		int length;//前缀和数组长度
		int *array;//前缀和数组指针

		void pretreatment()//预处理函数
		{
			for(int i=1; i<length; i++)
				*(array+i) += *(array+i-1);//递推式
		}

	public:

		PartialSum(int *arr,int len)//构造函数
		//arr:数组指针 len:数组长度
		{
			array = arr;
			length = len;
			pretreatment();//调用预处理函数
		}
		
		int query(int left, int right)//查询函数
		//left:左索引 right:右索引
		{
			return *(array+right)-*(array+left-1)*(left>0);
		}
};

二维前缀和

【预处理时间复杂度】O(n²)

【空间复杂度】O(n²)

【总时间复杂度】O(n² + m)【m为查询次数】

二维的前缀和与一维的差不多，也是前面所有项的和，只不过二维的前面项是以矩阵的形式一块一块地呈现

 //处理前
 1  2  3  4  5
 2  3  4  5  6
 3  4  5  6  7
 4  5  6  7  8

 //处理后
 1  3  6 10 15
 3  8 15 24 35
 6 15 27 42 60
10 24 42 64 90

【图解算法】 

二维前缀和

【数学表达式】

定义式

\small new[i][j]=\sum\limits_{p=0}\limits^i\sum\limits_{q=0}\limits^jold[p][q],i\geqslant 0,j\geqslant 0

在定义式中， new[i][j] 表示新数组索引为 k 和 j 的元素的值，old[p][q] 代表原数组索引为 p 和 q 的值

递推式

\small new[i][j]=new[i-1][j]+new[i][j-1]-new[i-1][j-1]+old[i][j],i\geqslant 1,j\geqslant 1

在递推式中，new[i][j] 表示新数组索引为 i 和 j 的元素的值，old[i][j] 代表原数组索引为 i 和 j 的值，

特别的，

当 i = 0 而 j != 0 时，new[i][j] = new[i][j-1]+old[i][j]，

当 j = 0 而 i != 0 时，new[i][j] = new[i-1][j]+old[i][j]，

当 i=0 且 j=0 时，new[i][j] = old[i][j]

【算法实现】

Python实现

class PartialSum2:#二维前缀和类
    def __init__(self, lis:list):#构造方法
        #lis:待处理的列表
        self.list = lis#前缀和列表
        self.x = len(lis)#前缀和列表x维长度
        self.y = len(lis[0])#前缀和列表y维长度
        self.__pretreatment()#调用预处理方法
    
    def __pretreatment(self):#预处理方法
        for i in range(self.x):
            for j in range(self.y):
                self.list[i][j] += self.list[i][j-1]*(j>0)+self.list[i-1][j]*(i>0)-self.list[i-1][j-1]*(i*j>0)#递推式

    def query(self, x1:int, y1:int, x2:int, y2:int):#查询方法
        #(x1,y1)为第1个索引坐标 (x2,y2)为第2个索引坐标
        return self.list[x2][y2]+self.list[x1-1][y1-1]*(x1*y1>0)-self.list[x1-1][y2]*(x1>0)-self.list[x2][y1-1]*(y1>0)

C/C++实现

class PartialSum2//二维前缀和类
{
	private:
		
		int x;//二维前缀和数组x维长度
		int y;//二维前缀和数组y维长度
		int *array;//二维前缀和数组
	
		void pretreatment()//预处理函数
		{
			for(int i=0;i<x;i++)
				for(int j=0;j<y;j++)
					*(array+i*y+j) += *(array+i*y+j-1)*(j>0)+*(array+(i-1)*y+j)*(i>0)-*(array+(i-1)*y+j-1)*(i*j>0);//递推式
		}

	public:

		PartialSum2(int *arr, int len_x, int len_y)//构造函数
		//arr:数组指针 len_x:数组x维长度 len_y:数组y维长度
		{
			array = arr;
			x = len_x;
			y = len_y;
			pretreatment();//调用预处理函数
		}

		int query(int x1, int y1, int x2, int y2)//查询函数
		//(x1,y1)为第1个索引坐标 (x2,y2)为第2个索引坐标
		{
			return *(array+x2*y+y2)+*(array+(x1-1)*y+y1-1)*(x1*y1>0)-*(array+(x1-1)*y+y2)*(x1>0)-*(array+x2*y+y1-1)*(y1>0);
		}
};

练手好题

【洛谷 P1387 最大正方形】

【洛谷 P3397 地毯】

二、差分算法

算法介绍

        差分算法也是一种对已知数据的预处理操作，目的是为了快速修改数据里的某个值或者某部分值，差分是指前缀和序列相邻项之间的差值

【预处理时间复杂度】与被处理数据的维数有关

【修改时间复杂度】O(1)

问题引入

        假设现在有一段长为 n 的序列，现在要求其索引为 left 和索引为 right 的值之间所有项都减去一个值，我们可以用循环进行遍历操作，如果要进行 m 次这样的操作，每次循环的时间复杂度为 O(n)，而要操作 m 次，那么总的时间复杂度就是 O(nm)，显然在修改的过程中序列有部分被重复遍历了 m 次，这是不必要的，如何省去这段重复过程从而加快修改的速度呢？

一维差分

【预处理时间复杂度】O(n)

【空间复杂度】O(n)

【总时间复杂度】O(n + m)【m为修改次数】

一维差分处理就是将每个位置的值修改为其与其前面一项的差（如下）

//处理前
1  3  6 10 15 21 28

//处理后
1  2  3  4  5  6  7

看到这里，细心的读者肯定已经发现，差分实际上就是前缀和的逆运算

但是啊，很显然，前缀和算法要比差分算法更容易理解一些，对差分数组里的元素操作的结果就是使原数组中同索引位置及之后的值全部进行相同的操作，原理很简单，差分数组的值是相邻两项之差，改变这个差值，后面所有的元素与前面的差值就都会有相同的改变

【图解算法】

一维差分

【数学表达式】

定义式

\small new[i]=old[i]-old[i-1],i\geqslant 1

特别的，当 i=0 时，new[i] = old[i]

逆推式

\small new[i]=new[i]-new[i-1],i\geqslant 1

特别的，当 i=0 时，new[i] = new[i]

【算法实现】

Python实现

class AdjacentDifference:#一维差分类
    def __init__(self, lis:list):#构造方法
        #lis:待处理列表
        self.list = lis#差分列表
        self.length = len(lis)#差分列表长度
        self.__pretreatment()#调用预处理方法

    def __pretreatment(self):#预处理方法
        for i in range(self.length-1,0,-1):
            self.list[i] -= self.list[i-1]#逆推式
    
    def modify(self, left:int, right:int, value:int):#修改方法
        #left:左索引 right:右索引 value:修改值
        self.list[left] += value
        if right+1 < self.length:
            self.list[right+1] -= value
        
    def inverse_operation(self):#返回方法
        #返回处理后的原列表
        lis = self.list[:]
        for i in range(1,self.length):
            lis[i] += lis[i-1]
        return lis

C/C++实现

class AdjacentDifference//一维差分类
{
    private:
    	
        int length;//差分数组长度
        int *array;//差分数组指针

		void pretreatment()//预处理函数
		{
			for(int i=length-1;i>0;i--)
				*(array+i) -= *(array+i-1);//逆推式
		}

	public:
		
		AdjacentDifference(int *arr, int len)//构造函数
		{
			array = arr;
			length = len;
			pretreatment();//调用预处理函数
		}
		
		void modify(int left, int right, int value)//修改函数
		//left:左索引 right:有索引 value:修改值
		{
			*(array+left) += value;
			if(right+1<length)*(array+right+1) -= value;
		}
		
		int *inverse_operation()//返回函数
		//返回逆运算后原数组的首项指针
		{
			for(int i=1;i<length;i++)
				*(array+i)=*(array+i-1)+*(array+i);
			return array;
		}
};

二维差分

【预处理时间复杂度】O(n²)

【空间复杂度】O(n²)

【总时间复杂度】O(n² + m)【m为修改次数】

二维差分和一维差分类似，原理不再赘述

 //处理前
 1  3  6 10 15
 3  8 15 24 35
 6 15 27 42 60
10 24 42 64 90

 //处理后
 1  2  3  4  5
 2  3  4  5  6
 3  4  5  6  7
 4  5  6  7  8

【图解算法】 

二维差分

【数学表达式】

定义式

\small new[i][j]=old[i][j]+old[i-1][j-1]-old[i][j-1]-old[i-1][j],i\geqslant 1,j\geqslant 1

特别的，

当 i = 0，j != 0 时，new[i][j] = old[i][j] - old[i][j-1]

当 j = 0，i != 0 时，new[i][j] = old[i][j] - old[i-1][j]

当 i = 0，j = 0 时，new[i][j] = old[i][j]

逆推式

\small new[i][j]=new[i][j]+new[i-1][j-1]-new[i][j-1]-new[i-1][j],i\geqslant 1,j\geqslant 1

特别的，

当 i = 0，j != 0 时，new[i][j] = new[i][j] - new[i][j-1]

当 j = 0，i != 0 时，new[i][j] = new[i][j] - new[i-1][j]

当 i = 0，j = 0 时，new[i][j] = new[i][j]

【算法实现】

Python实现

class AdjacentDifference2:#二维差分类
    def __init__(self, lis:list):#构造方法
        #lis:待处理列表
        self.list = lis#差分列表
        self.x = len(lis)#差分列表x维长度
        self.y = len(lis[0])#差分列表y维长度
        self.__pretreatment()#调用预处理方法

    def __pretreatment(self):#预处理方法
        for i in range(self.x-1,-1,-1):
            for j in range(self.y-1,-1,-1):
                self.list[i][j]+=self.list[i-1][j-1]*(i*j>0)-self.list[i-1][j]*(i>0)-self.list[i][j-1]*(j>0)#逆推式
    
    def modify(self, x1:int, y1:int, x2:int, y2:int, value:int):#修改方法
        #(x1,y1)为第1个索引坐标 (x2,y2)为第2个索引坐标 value:修改值
        self.list[x1][y1] += value
        if x2+1 < self.x:self.list[x2+1][y1] -= value
        if y2+1 < self.y:self.list[x1][y2+1] -= value
        if x2+1 < self.x and y2+1 < self.y:self.list[x2+1][y2+1] += value
        
    def inverse_operation(self):#返回方法
        #返回逆运算后的原列表
        lis = eval(str(self.list))
        for i in range(self.x):
            for j in range(self.y):
                lis[i][j] += lis[i][j-1]*(j>0)+lis[i-1][j]*(i>0)-lis[i-1][j-1]*(i*j>0)
        return lis

C/C++实现

class AdjacentDifference2//二维差分类
{
	private:

		int x;//差分数组x维长度
		int y;//差分数组y维长度
		int *array;//二维差分数组

		void pretreatment()//预处理函数
		{
			for(int i=x-1;i>-1;i--)
				for(int j=y-1;j>-1;j--)
					*(array+i*y+j) += *(array+(i-1)*y+j-1)*(i*j>0)-*(array+(i-1)*y+j)*(i>0)-*(array+i*y+j-1)*(j>0);//逆推式
		}

	public:

		AdjacentDifference2(int *arr, int len_x, int len_y)//构造函数
		{
			array = arr;
			x = len_x;
			y = len_y;
			pretreatment();//调用预处理函数
		}

		void modify(int x1, int y1, int x2, int y2, int value)//修改函数
		//(x1,y1)为第1个索引坐标 (x2,y2)为第2个索引坐标 value:修改值
		{
			*(array+x1*y+y1) += value;
			if(x2+1<x)*(array+(x2+1)*y+y1) -= value;
			if(y2+1<y)*(array+x1*y+y2+1) -= value;
			if(x2+1<x&&y2+1<y)*(array+(x2+1)*y+y2+1) += value;
		}

		int *inverse_operation()//返回函数
		//返回逆运算后原数组的首项指针
		{
			for(int i=0;i<x;i++)
				for(int j=0;j<y;j++)
					*(array+i*y+j)+=*(array+i*y+j-1)*(j>0)+*(array+(i-1)*y+j)*(i>0)-*(array+(i-1)*y+j-1)*(i*j>0);
			return array;
		}
};

练手好题

【洛谷 P2367 语文成绩】

三、总结

        前缀和算法与差分算法都属于对数据预处理的方法，前缀和算法是为了快速地查询数据中的某个值或某个区间值的和，而差分算法是为了快速修改数据中的某个值或某区间内的值，两者互为逆运算！虽然本文章只涉及到了一维和二维的两种算法，但相信大家在看懂了算法的原理后，这两种算法的更高维度版本也可以轻而易举地写出来！

【都看到这里了，不妨点个赞吧！】 

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布