1.什么是数据结构
- 数据结构是存储，组织数据的方式
- 精心选择的数据结构可以带来更高的运行或者存储效率
- 数据结构是很多算法得以进行的载体
比如我们常见的数组，链表，图，二叉树等等都是数据结构。
数组是内存上一块连续的空间，指定长度为一个数组的大小，如果超过这个长度，就会出现数组越界的情况。因为数组是连续的空间，那么默认某个节点的内存加1就是下一个数据节点，并且我们提前给数组标注了“下标”，所以很容易找到某个元素，即便于寻址。既然我们数组是连续的空间，那么对于数组中的数据进行增删是比较费劲的，因为需要对插入或者删除位置后边的所有的元素统一进行移动。所以数组是便于寻址，不便于增删数据。
链表内存上不一定连续，链表中的每个节点中存储着节点数据和下一个节点的“地址”，根据存储的地址进行寻址。它没有所谓的下标，没有办法一下子定位到某个元素，我们需要一个一个的遍历。但是正因为如此，我们增删数据时不依赖空间上的连续性问题，直接修改节点中的那个“地址”来进行数据的增删。所以链表是不便于寻址，但是便于增删数据。
图和二叉树比较复杂，此处先不讲。
那么我们通过一个案例来更清晰的理解数据结构的作用。
2. 案例：查询数组上L~R位置上的累加和(L<R)
举例说明
数组Array.png
如上图所示，我想求得1～3位置上的累加和，那我们可以看到是 3+ 3+ 10 = 16.
如题，我们该怎么做呢？
其实，有两种想法，仅供参考。
-
我们列一个二维数组，或者一个表格，把所有的L~R的累加和都记录下来，然后我们查询时取出来即可。
L～R的累加和表格.png
从图上可以看到凡是L>R的地方都是不成立的，去掉，其余任意一个L~R的累加和都可以直接取出来，这个适合于查询量巨大的情况，我们对于这点空间消耗是能够接受的，以时间换空间。
-
第二种方式我用一个等长的数组存储0位置到某个位置的累加和。
前缀和数组H.png
从图上我们可以看出来，每个位置存的都是0～该位置的累加和，我们称为前缀和数组。
那么我们要求的L~R的累加和就可以这样算
- L == 0时, 累加和= H[R]
- L != 0时, 累加和= H[R] - H[L-1]
第二种方式在空间上大大节约了，但是还需要再做一步计算，所以适用于查询量不那么巨大的情况。
前缀和的代码比较简单，列一下吧。
//求前缀和数组
public static int[] preSumArray(int[] arr){
int n = arr.length;
int[] preSumNum = new int[n];
preSumNum[0] =arr[0];
for(int i = 1; i < n; i++){
preSumNum[i] = preSumNum[i-1] + arr[i];
}
return preSumNum;
}
//L~R的累加和计算
public static int sumOfLtoR(int[] preSumArray, int L, int R){
if(L>R){
throw new RuntimeException("L不能大于R");
}
if(L == 0){
return preSumArray[R];
}else{
return preSumArray[R] - preSumArray[L-1];
}
}
