数组
数组可能是我们学习的第一个数据结构，虽然它很简单，但是如果从查询和更新的角度思考它，会发现很有意思的东西。
约定
a[i]:普通数组

s[i]:普通数组的前缀和数组

c[i]:普通数组的差分数组
普通数组
对于普通的一组有序数据，a[i]存第$i$个数据。

单点查询：$O(1)$

区间查询：$O(n)$

单点更新：$O(1)$

区间更新：$O(n)$
差分数组
c[i] = a[i] - a[i - 1]。
单点查询：$O(1)$

区间查询：$O(n)$

差分数组可以求出原数组的前缀和，$s[i] = \sum_{j=1}^{i}(i-j+1) \cdot c_{j}$,但复杂度$O(n)$，并不具有优势。

单点更新：$O(1)$

区间更新：$O(1)$ c[a] += k, c[b + 1] -= k（更新区间$[a,b]$）
前缀和数组
a[i] = s[i] - s[i - 1]，a[i]相当于是s[i]的差分数组。
单点查询：$O(1)$

区间查询：$O(1)$

单点更新：$O(n)$

区间更新：$O(n)$
总结
普通数组和前缀和数组各有优劣。普通数组区间操作均为$O(n)$，单次操作均为$O(1)$,相比于普通数组，前缀和数组可以快速进行区间查询，复杂度$O(1)$,但是牺牲了区间更新，复杂度$O(n)$。
差分数组性能优秀，只有区间查询复杂度是$O(n)$，其余均为$O(1)$，完全优于普通数组。这个特性可以被用于优化树状数组，让树状数组可以同时区间更新，区间查询。
扩展：二维数组

普通数组的二维数组还是很普通。
二维前缀和数组s[i][j]表示$\sum_{k = 1}^{i}\sum_{l = 1}^{j}a[k][l]$,递推式为s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
二维差分数组的定义很不直观，但类比a[i][j]相对于s[i][j],可以得到递推式:c[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

从二维差分数组推导二维前缀数组的公式: $s[i][j] = \sum_{k = 1}^{i}\sum_{l = 1}^{j}\sum_{u = 1}^{k}\sum_{v = 1}^{l}c[u][v]$ （复杂度$O(n ^ {4})$）可以化简成 $s[i][j] = \sum_{k = 1} ^ {i}\sum_{l = 1}^{j} (i - k + 1)(j - l + 1)c[k][l]$ （复杂度$O(n ^ {2})$）, 用二维树状数组可以进一步达到$O(log^{2}n)$

四数之和 4sum

第十一章  34
给一个包含 n 个数的整数数组 S，在 S 中找到所有使得和为给定整数 target 的四元组(a, b,c,d)。

注意事项：

四元组(a, b, c, d)中，需要满足 a <= b <= c <= d。

答案中不可以包含重复的四元组。

样例：

例如，对于给定的整数数组 S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：

(-1, 0, 0, 1)

(-2, -1, 1, 2)

(-2, 0, 0, 2)
解题思路：
想参照之前的一题 3Sum 的解法来解决，结果超时了。换个思路，空间换时间。既然有四个数，那就把前两个数之和和后两个数之和分别当做一个数。现在要求的就是在一个列表中哪两个数的和为特定值。可以先遍历一遍列表，存值和它的下标的键值对，第二遍遍历列表寻找（目标值-当前值）是否在之前的键值对中，如果在就是符合的一组解。
// An highlighted block

class Solution(object):
    def fourSum(self,nums,target):
        if len(nums) < 4:
            return []
        result =set()
        sumsIndexes = {}
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j] in sumsIndexes:
                    sumsIndexes[nums[i]+nums[j]].append((i,j))
                else:
                    sumsIndexes[nums[i]+nums[j]]=[(i,j)]
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                sumNeeded = target-(nums[i]+nums[j])
                if sumNeeded in sumsIndexes:
                    for index in sumsIndexes[sumNeeded]:
                        if index[0]>j:
                            result.add(tuple(sorted([nums[i],nums[j],nums[index[0]],nums[index[1]]])))
        result = [list(l) for l in result]
        return result

if __name__ =="__main__":
    a=Solution()
    b=[1,0,-1,0,-2,2]
    c = 0
    print(a.fourSum(b,c))

----2020/3/12
对一维整型数组a的正确说明是 #define SIZE 10 (换行) int a[SIZE];说法是否正确？
正确答案: A

正确

错误

解析： #define SIZE 10

它的作用是指定标识符SIZE 来代替表达式10。
----已知二维数组A[1: 4, 1: 6]采用列序为主序方式存储，每个元素占用4个存储单元，并且A[3，4]的存储地址为1234，元素A[1, 1]的存储地址是（）
正确答案: A

1178

1190

1278

1290

解析：a11+(3*4+2)*4=1234。这样就可以得到a11
----以下定义和初始化的两数组a1和a2，那么下列说法正确的是( )。

char a1[]= “program”;

char a2[]={‘p’,‘r’,‘o’,‘g’,‘r’,‘a’,‘m’}

正确答案: D

a1和a2完全相同

a1和a2不同，a1是指针

a1和a2存储单元的数目相同

a1和a2不同，a1的存储单元数目多
解析：sizeof(a1)=8,sizeof(a2)=7,a1存储单元数目多。
----c中，二维数组初始化的方法是:int a[3][3]={{1},{2},{3}};说法是否正确？
正确答案: A

正确

错误

解析：正确的， 最外层的 { … } 会初始化 a[] 即第一维。
----已知数组D的定义是int D[4][8];,现在需要把这个数组作为实参传递给一个函数进行处理。下列说明汇总可以作为对应的形参变量说明的是（）。

正确答案: C D

int D[4][]

int *s[8]

int(*s)[8]

int D[][8]
解析：int *s[8]; //定义一个指针数组，该数组中每个元素是一个指针，每个指针指向哪里就需要程序中后续再定义了。

int (*s)[8]; //定义一个数组指针，该指针指向含8个元素的一维数组（数组中每个元素是int型）。
区分int *p[n]; 和int (*p)[n]; 就要看运算符的优先级了。

int * p[n]; 中，运算符[ ]优先级高，先与p结合成为一个数组，再由int *说明这是一个整型指针数组。

int (*p)[n]; 中( )优先级高，首先说明p是一个指针，指向一个整型的一维数组。
2020/3/13

----设有一个长度为n的顺序表，要在第i（从1开始）个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（   ）。

正确答案: A

n-i+1

n-i

n-i-1

i
解析：1 2 3 4 5

n = 5

要在第i=2个元素之前插入

则n-i=3

而实际插入位置为：

1 [ ] 2 3 4 5

所以是n-i+1
----下面哪项不是链表优于数组的特点?

正确答案: D

方便删除

方便插入

长度可变

存储空间小

解析：链表：方便插入和删除，包含数据和指针域，存储空间大。
----假设有60行70列的二维数组 a[1 …60, 1…70 ] 以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素 a[ 32,58 ] 的存储地址为
正确答案: A

16902

16904

14454

以上答案均不对
解析：

第32行第58列的元素 表示为 a[   32,58   ] ，但是我们习惯写成a【31】【57】

二维数组可以表示为A【60】【70】 （60行70列）

a[   31,57   ]

以列序为主： （5760+31） * 2+10000= 16902

以行序为主： （3170+57）*2 +10000= 14454
----数组A[0…4,-1…-3,5…7]中含有元素的个数()

正确答案: B

55

45

36

16

解析：三维数组，533=45
----2020/3/14
----数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（）。
正确答案: D

r－f

（n＋f－r）% n

n＋r－f

（n＋r－f）% n
解析：
----数组常用的两种基本操作是(    )。

正确答案: C

建立与删除

删除与查找

查找与修改

插入与索引
解析：删除的时间复杂度比较大，链式结构会采用删除。
----在前提:var arr=[1,3,2]下，下面哪个操作会返回一个数组，并且不是arr？

正确答案: C

arr.push(3)

arr.reverse()

[].concat.call(arr,[])

[].sort.call(arr)
解析：1.contact函数的功能是：连接两个或多个数组。将返回连接数组后的副本，不影响原来的数组 2.call函数调用一个对象的一个方法，以另一个对象替换当前对象 3.js中的函数其实是对象，函数名是对函数对象的引用。
----对有序数组{2、11、15、19、30、32、61、72、88、90、96}进行二分查找，则成功找到15需比较（）次

正确答案: C

3

4

2

5

解析：C

0     1      2     3      4     5     6       7     8     9   10

2、11、15、19、30、32、61、72、88、90、96

第一次  index=（0+10）/2=5   对应32 ； 比15大  所以下次范围是 0到4

第二次  index=（0+4）/2=2  对应15   找到

后缀数组是一个处理字符串的有力工具，对于常见的字符串匹配、模式匹配，求子串前缀等问题，后缀数组都有很好的效果。

但是好难懂啊。。搜了国家集训队的论文，看了挑战书上的介绍，看了好长时间才稍微有一点感觉。。就20多行的代码看了N久才理解…大概是我太弱了。

根据论文先来总结一下后缀数组的主要内容吧。

1、基本定义 

子串：字符串S的子串r[i…j]，i≤j，表示r串中从i到j这一段形成的字符串。 

后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。 

大小比较：字符串的比较，是指通常所说的字典序比较，比较规则是这样的：



对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]
如果u[i] = v[i] 则令i+1，继续比较
否则 若u[i] < v[i] 则认为u<v； u[i] > v[i]，则认为 u > v。比较结束。
如果i>min(len(u),len(v))仍然比较不出结果，那就比较uv的长度，长度大的那个字符串就是更大的串。

后缀数组：后缀数组指的是将某个字符串的所有后缀按字典序排序后得到的数组。不过数组中并不需要直接保存所有的后缀字符串，只要记录对应的起始位置就好了。下文中，我们用S[i…]来表示字符串S从位置i开始的后缀。 

名次数组：名次数组Rank[i]保存的是S[i]在所有后缀中从小到大排列的名字。

简单地说，后缀数组是“排第几的是谁？”名次数组是“你排第几？”。

举例： 


大家可以根据这个字符串，自己计算一下Rank。

后缀数组的计算方法——倍增算法 

假设我们要计算长度为n的字符串S的后缀数组，最朴素的做法就是把所有后缀进行排序，将n个长度为O(n)的字符串进行排序的复杂度为O(n²logn)。而如果灵活运用所有的字符串都是S的后缀这一性质，就可以得到更高效的算法。

该算法的基本思想是倍增。 

首先计算每个位置开始长度为2的子串的顺序，再利用这个结果计算长度为4的子串顺序，接下来计算长度为8的子串的顺序，不断倍增，直到长度大于等于n，就得到了所有的后缀数组。并且这些子串一定已经比较出了大小，即Rank[]中已经没有相同的值，那么此时的Rank值就是最后的结果。每一次排序都利用上次长度为2^(k-1)的字符串的Rank值，那么长度为2^k的字符串就可以用两个长度为2^(k-1)的字符串的排名作为关键字表示，然后进行排序，就得出了长度为2^k的字符串的Rank值。







using namespace std;
const int MAXN = 100000;
int n,k;
int Rank[MAXN+1];
int tmp[MAXN+1];

//比较(rank[i],rank[i+k])和(rank[j],rank[j+k])
bool compare_sa(int i ,int j)
{
    if (Rank[i]!= Rank[j]) return Rank[i] < Rank[j];
    else
    {
        int ri = i+k<=n? Rank[i+k] : -1;
        int rj = j+k<=n? Rank[j+k] : -1;
        return ri < rj;
    }
}

//计算字符串S的后缀数组
void construct_sa(string S,int *sa)
{
    n = S.length();
    //rank直接获取字符的编码
    for(int i = 0;i<=n;i++)
    {
        sa[i] = i;
        Rank[i] = i < n ? S[i] : -1;
    }
    //利用对长度为k的排序结果对长度为2k的排序
    for(k = 1; k <= n; k *= 2)
    {
        sort(sa,sa+n+1,compare_sa);
        //先在temp中临时存储新计算的rank，再转存回rank中
        tmp[sa[0]] = 0;
        for(int i = 1 ; i <= n; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1],sa[i])? 1: 0);
        for(int i = 0 ; i <= n; i++)
            Rank[i] = tmp[i];
    }
}

在做hdoj的1009，本来这道题目不是很难，可是对于struct动态数组操作不是很熟，做了很久，在这里记录一下，避免下次继续出错。
FatMouse' Trade
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 25384 Accepted Submission(s): 8029



Problem Description
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.

The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of
 cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.




 
Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case
 is followed by two -1's. All integers are not greater than 1000.




 
Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.




 
Sample Input

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1




 
Sample Output

13.333
31.500



代码如下：
#include<stdio.h>
#include<algorithm>
using namespace std;

struct trade{
	int j;
	int f;
};

bool compare(const trade &a, const trade &b){
	return double(a.j)/double(a.f)>double(b.j)/double(b.f);
}

void main(){
	int m,n;
	double sum;
	while(1){
		sum=0.0;
		scanf("%d %d",&m,&n);
		if(m==-1)
			break;
		trade* array=new trade[n];
		for(int i=0; i<n; i++){
			scanf("%d %d",&array[i].j,&array[i].f);
		}
		sort(array,array+n,compare);
		for(int j=0; j<n; j++){
			if(m<array[j].f){
				sum+=double(array[j].j)/double(array[j].f)*m;
				break;
			}
			m-=array[j].f;
			sum+=array[j].j;
		}
		printf("%.3f\n",sum);
		delete []array;
	}
}



其中，创建动态struct数组
struct struct_name * struct_array = new struct_name[struct_array_len];
输入struct数组元素值，记得不要落下&
scanf("%d",&struct_array[i].struct_member);
排序
sort(struct_array,struct_array+struct_array_len,compare);
释放
delete []struct_array;