1.1 数组

数组是相同数据类型元素的集合所组成的一种数据结构，数组在内存中是连续的，它的大小在初始化的时候就已经固定，数组一旦创建，它的长度是不能改变的，常见的动态数组ArrayList并不是改变了数组的长度，而是又重新创建了一个数组。可以通过数组的下标来修改数组，数组的下标一般都是从0开始的，比如a[0]是数组的第一个元素，a[5]是数组的第6个元素等，如图1-1所示。

最常见的数组是一维数组，它的定义如下（这里以Java为例）。除了一维数组还有二维数组、三维数组等，这里就不再过多介绍。

1.1.1 滚动数组

滚动数组也是使用数组来实现的，它不是一种数据结构，而是一种算法优化思想，滚动数组的作用在于优化空间，让数组滚动起来，每次使用固定的几个存储空间，比如常见的斐波那契数列：f[n]=f[n-1]+f[n-2]，普通的写法如下：

如图1-2所示，虽然我们定义了一个很长的数组，但每次只用最近的3个，前面的都浪费了，所以可以使用滚动数组，只需要一个长度为3的数组即可。

上面讲的是一维数组，对于二维数组有时候也可以使用滚动数组。这需要结合具体的示例来讲解，具体将在第11章动态规划中进行介绍。

1.1.2 差分数组

假设给定一个数组nums，先对区间[a,b]中的每个元素加3，再对区间[c,d]中的每个元素减5等，这样非常频繁的区间修改，常规的做法可以一个个计算，代码如下：

频繁对数组的一段区间增加或减去同一个值，如果一个个去操作，效率会很低，可以使用差分数组，差分数组就是原始数组相邻元素之间的差。定义差分数组d[n]，那么可以得到：d[i]=nums[i]-nums[i-1]，其中d[0]=nums[0]，如图1-3所示。

可以看到原数组就是差分数组的前缀和。

有了差分数组，如果对区间[a,b]中的每个元素加3，就不需要再一个个操作，只需要在差分数组的两端进行修改即可，如图1-4所示。

1.1.3 二维差分数组

我们可以把一维差分数组看作是一条直线，只需要用后面的值减去前面的值，就可以构造差分数组。而二维差分数可以把它看作是一个平面，如图1-5所示，它的定义如下：

如果想获取原数组，根据上面的公式可以得到：

如图1-6所示，以（x1,y1）为左上角，（x2,y2）为右下角构成一个区间，如果对这个区间内的每个元素增加val，只需要执行下面四步即可。

1.1.4 树状数组

假设有一个数组，对它进行大量的修改和查询，修改的是数组中某一个元素的值，查询的是数组中任意一个区间的和。对于修改比较简单，时间复杂度是O(1)，而查询的时间复杂度是O(n)。大家可能会建议使用前缀和来优化，前缀和查询的时间复杂度确实是O(1)，但如果我们修改某一个元素的时候，前缀和后面的值也都要修改，时间复杂度是O(n)。那么有没有一种方式可以让修改和查询时间复杂度降一个数量级呢？有的，那就是树状数组，它的修改和查询时间复杂度都是O(logn)，综合来看还是不错的。如图1-7所示，这是一个树状数组，其中数组a[]是原始数组，数组c[]是树状数组。

令树状数组每个位置保存的是子节点值的和，则有：

通过上面的公式可以发现一个规律：

比如c[6]，6的二进制是（110），最右边有1个0，那么k就等于1，所以：

再比如c[4]，4的二进制是（100），最右边有2个连续的0，那么k就等于2，所以：

通过图1-7可以发现，在树状数组c[i]中，如果i是奇数，c[i]就在第0层，也就是树状数组的叶子节点，并且c[i]=a[i]。如果i不是奇数，那么在i的二进制位中，它的右边有几个0, c[i]就在第几层。我们定义函数int lowBit (int x)表示只保留x的二进制中最右边的1，其他位置全部变为0，比如：

函数int lowBit (int x)的代码如下：

这个很好理解，比如数字12和-12，它们的二进制如下，只要对它们进行&运算，就是我们想要的结果。

我们令s[i]表示原始数组a的前i项和，通过图1-7可以找出s和c的关系：

通过上面等式的关系可以得出规律：

这里的k1,k2,k3,……,kn都是2的k次方，实际上就是不断地抹去i的二进制中右边的1，直到i变成0为止。比如数字7，它的二进制是111，所以s[111]=c[111]+c[110]+c[100]（这里的数字是用二进制表示），也就是s[7]=c[7]+c[6]+c[4]。

这个就是求和，如果我们想要计算数组区间[left,right]的和，可以像下面这样调用。

树状数组的求和我们知道了，那么修改呢（这里先讨论单点修改）。如果树状数组的一个节点值被修改了，那么它的父节点值都要改变，如图1-8所示，当a[5]的值被修改后，那么c5、c6以及c8都要修改。

如果要更改c[i]的值，只需要找到c[i]的父节点以及其父节点的父节点，一直往上走，直到根节点，全部修改即可。通过图1-8可以发现，c[i]的父节点就是c[i+lowBit(i)]，所以需要以c[i]为起点，通过循环不断地往上找父节点，然后修改，来看一下树状数组的完整代码：

1. 区间更新，单点查询

对于数组更新和查找可以分为下面几类：

•单点更新，单点查询。

•单点更新，区间查询。

•区间更新，单点查询。

•区间更新，区间查询。

对于单点更新，单点查询，原始数组就可以做，不需要构建树状数组。而单点更新，区间查询在前面刚刚介绍过，这里来看一下区间更新，单点查询。如果想要区间更新，需要构建差分数组，在前面1.1.2小节差分数组中讲过，如果要更新原始数组区间的值，只需要更新差分数组两边的值即可。其中差分数组的前缀和就是数组a中某个元素的值，来看一下代码：

2. 区间更新，区间查询

区间更新可以使用差分数组，那么区间查询呢？假设求数组a的前n项和，来看一下公式推导，如图1-9所示。

a是原数组，d是差分数组，这里需要构建两个树状数组，其中d1[i]=d[i]，d2[i]=d[i]∗(i-1)。

前面介绍的是一维树状数组，大家也可以研究一下二维树状数组，这里就不再介绍。区间更新和区间查询除了使用树状数组，还可以使用线段树，线段树不光可以区间求和，还可以求区间最大值、区间最小值，功能要比树状数组更强大，关于线段树会在1.6.6小节线段树中介绍。