一维差分数组
假设给你一个数组 nums ,先对区间 [a,b] 中每个元素加 3 ,在对区间 [c,d] 每个元素减 5 …… ,这样非常频繁的区间修改,常规的做法可以一个个计算。
频繁对数组的一段区间进行增加或减去同一个值,如果一个个去操作,很明显效率很差,我们可以使用差分数组,差分数组就是原始数组相邻元素之间的差。定义差分数组 d[n] ,我们可以得到: d[i] = nums[i] − nums[i−1] ,其中 d[0] = nums[0] ,如下图所示。
我们可以看到原数组就是差分数组的前缀和。
有了差分数组,如果对区间 [a,b] 每个元素加 3 ,不需要在一个个操作,只需要在两端修改即可,如下图所示。
来看下代码:
二维差分数组
我们把一维差分数组看做是一条直线,只需要用后面的值减去前面的值就可以构造差分数组。而二维差分数可以把他看做是一个平面,如下图所示,他的定义如下:
如果想获取原数组,根据上面的公式可以得到:
如下图所示,以 (x1,y1) 为左上角, (x2,y2) 为右下角构成一个区间,如果对这个区间内的每个元素增加 val ,只需要执行下面四步即可。
代码如下:
数组,滚动数组,差分数组,树状数组 | |
链单向表,双向链表,循环链表,跳表,异或链表 | |
队列,循环队列,双端队列 | |
栈 | |
散列表 | |
二叉树,二叉搜索树,AVL树,红黑树,字典树,哈夫曼树,线段树,笛卡尔树 | |
堆 | |
图的介绍,图的遍历,Dijkstra算法,Bellman-Ford算法,SPFA算法,Floyd算法,Prim算法,Kruskal算法,Boruvka算法,拓扑排序 |