目录
 
1、前缀和
2、前缀和算法有什么好处？
3、二维前缀和
4、差分
5、一维差分
6、二维差分
在这里插入图片描述
 

 
1、前缀和
 
 
 
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。
 
 
 
 
2、前缀和算法有什么好处？
 
先来了解这样一个问题：
 
输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。
 
我们很容易想出暴力解法，遍历区间求和。
 
代码如下：
 
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--)
{
    int l,r;
    int sum=0;
    scanf("%d%d",&l,&r);
    for(int i=l;i<=r;i++)
    { 
        sum+=a[i];
    }
    printf("%d\n",sum);
}
 
这样的时间复杂度为O(n*m)，如果n和m的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大提高了运算效率。
 
具体做法：
 
首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
 
求前缀和运算：
 
const int N=1e5+10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i=1;i<=n;i++)
{ 
    sum[i]=sum[i-1]+a[i];   
}
 
然后查询操作：
 
 scanf("%d%d",&l,&r);
 printf("%d\n", sum[r]-sum[l-1]);
 
对于每次查询，只需执行sum[r]-sum[l-1] ，时间复杂度为O(1)
 
原理
 
sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
 sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
 sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
 
图解
 
 这样，对于每个询问，只需要执行 sum[r]-sum[l-1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。
 
我们把它叫做一维前缀和。
 
总结：
 
 练习一道题目
 输入一个长度为n的整数序列。
 接下来再输入m个询问，每个询问输入一对l, r。
 对于每个询问，输出原序列中从第l个数到第r个数的和。
 输入格式
 第一行包含两个整数n和m。
 第二行包含n个整数，表示整数数列。
 接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
 输出格式
 共m行，每行输出一个询问的结果。
 数据范围
 1≤l≤r≤n,
 1≤n,m≤100000,
 −1000≤数列中元素的值≤1000
 输入样例：
 5 3
 2 1 3 6 4
 1 2
 1 3
 2 4
 输出样例：
 3
 6
 10
 代码：
 
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
    }

    return 0;
}
 
3、二维前缀和
 
如果数组变成了二维数组怎么办呢？
 
先给出问题：
 
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
 
同一维前缀和一样，我们先来定义一个二维数组s[][], s[i][j]表示二维数组中，左上角(1,1)到右下角( i,j )所包围的矩阵元素的和。接下来推导二维前缀和的公式。
 
先看一张图：
 
 
紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积, 绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。
 
 从图中我们很容易看出，整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 重复加的红色的面积s[i-1][j-1]+小方块的面积a[i][j];
 
因此得出二维前缀和预处理公式
 
s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1]
 
接下来回归问题去求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和。
 
如图：
 
 
紫色面积是指 ( 1,1 )左上角到(x1-1,y2)右下角的矩形面积 ，黄色面积是指(1,1)左上角到(x2,y1-1)右下角的矩形面积；
 
不难推出：
 
 
绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1]
 
因此二维前缀和的结论为：
 
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
 s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]
 
总结：
 
 
练习一道完整题目：
 输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
 
对于每个询问输出子矩阵中所有数的和。
 
输入格式
 第一行包含三个整数n，m，q。
 
接下来n行，每行包含m个整数，表示整数矩阵。
 
接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。
 
输出格式
 共q行，每行输出一个询问的结果。
 
数据范围
 1≤n,m≤1000,
 1≤q≤200000,
 1≤x1≤x2≤n,
 1≤y1≤y2≤m,
 −1000≤矩阵内元素的值≤1000
 输入样例：
 3 4 3
 1 7 2 4
 3 6 2 8
 2 1 2 3
 1 1 2 2
 2 1 3 4
 1 3 3 4
 输出样例：
 17
 27
 21
 
代码：
 
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
       scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
    while(q--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
    }
    return 0;
}
 
4、差分
 
 
 
5、一维差分
 
类似于数学中的求导和积分，差分可以看成前缀和的逆运算。
 
差分数组：
 
首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];
 
然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];
 
使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]
 
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
 
考虑如何构造差分b数组？
 
最为直接的方法
 
如下：
 
a[0 ]= 0;
 
b[1] = a[1] - a[0];
 
b[2] = a[2] - a[1];
 
b[3] =a [3] - a[2];
 
........
 
b[n] = a[n] - a[n-1];
 
图示:
 
 
我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组 。
 
知道了差分数组有什么用呢？ 别着急，慢慢往下看。
 
话说有这么一个问题：
 
给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;
 
暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。有没有更高效的做法吗? 考虑差分做法，(差分数组派上用场了)。
 
始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
 
首先让差分b数组中的 b[l] + c ,通过前缀和运算，a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c;
 
然后我们打个补丁，b[r+1] - c, 通过前缀和运算，a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;
 
为啥还要打个补丁？
 
我们画个图理解一下这个公式的由来:
 
 b[l] + c，效果使得a数组中 a[l]及以后的数都加上了c(红色部分)，但我们只要求l到r区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分)，这样对于a[r] 以后区间的数相当于没有发生改变。
 
因此我们得出一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。
 
总结：
 
 
题目练习： AcWing 797. 差分
 
输入一个长度为n的整数序列。
 接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。
 请你输出进行完所有操作后的序列。
 输入格式
 第一行包含两个整数n和m。
 第二行包含n个整数，表示整数序列。
 接下来m行，每行包含三个整数l，r，c，表示一个操作。
 输出格式
 共一行，包含n个整数，表示最终序列。
 数据范围
 1≤n,m≤100000,
 1≤l≤r≤n,
 −1000≤c≤1000,
 −1000≤整数序列中元素的值≤1000
 输入样例：
 6 3
 1 2 2 1 2 1
 1 3 1
 3 5 1
 1 6 1
 输出样例：
 3 4 5 3 4 2
 AC代码
 
//差分 时间复杂度 o(m)
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N]; 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];      //构建差分数组
    }
    int l,r,c;
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&c);
        b[l]+=c;     //表示将序列中[l, r]之间的每个数加上c
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++) 
    {
        b[i]+=b[i-1];  //求前缀和运算
        printf("%d ",b[i]);
    }
    return 0;
}
 
6、二维差分
 
如果扩展到二维，我们需要让二维数组被选中的子矩阵中的每个元素的值加上c,是否也可以达到O(1)的时间复杂度。答案是可以的，考虑二维差分。
 
a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组
 
原数组： a[i][j]
 
我们去构造差分数组： b[i][j]
 
使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和。
 
如何构造b数组呢？
 
其实关于差分数组，我们并不用考虑其构造方法，因为我们使用差分操作在对原数组进行修改的过程中，实际上就可以构造出差分数组。
 
同一维差分，我们构造二维差分数组目的是为了 让原二维数组a中所选中子矩阵中的每一个元素加上c的操作，可以由O(n*n)的时间复杂度优化成O(1)
 
已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角，以(x2,y2)为右下角所围成的矩形区域;
 
始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。
 
假定我们已经构造好了b数组，类比一维差分，我们执行以下操作
 来使被选中的子矩阵中的每个元素的值加上c
 
b[x1][y1] + = c;
 
b[x1,][y2+1] - = c;
 
b[x2+1][y1] - = c;
 
b[x2+1][y2+1] + = c;
 
每次对b数组执行以上操作，等价于：
 
for(int i=x1;i<=x2;i++)
  for(int j=y1;j<=y2;j++)
    a[i][j]+=c;
 
我们画个图去理解一下这个过程：
 
 
b[x1][ y1 ] +=c ; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
 b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
 b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
 b[x2+1][y2+1]+=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。
 
 我们将上述操作封装成一个插入函数:
 
void insert(int x1,int y1,int x2,int y2,int c)
{     //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
 
我们可以先假想a数组为空，那么b数组一开始也为空，但是实际上a数组并不为空，因此我们每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作，就成功构建了差分b数组.
 
这叫做曲线救国。
 
代码如下：
 
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          insert(i,j,i,j,a[i][j]);    //构建差分数组
      }
  }
 
当然关于二维差分操作也有直接的构造方法，公式如下：
 
b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]
 
二维差分数组的构造同一维差分思维相同，因次在这里就不再展开叙述了。
 
总结：
 
 
题目练习： AcWing 798. 差分矩阵
 输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。
 每个操作都要将选中的子矩阵中的每个元素的值加上c。
 请你将进行完所有操作后的矩阵输出。
 输入格式
 第一行包含整数n,m,q。
 接下来n行，每行包含m个整数，表示整数矩阵。
 接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。
 输出格式
 共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
 数据范围
 1≤n,m≤1000,
 1≤q≤100000,
 1≤x1≤x2≤n,
 1≤y1≤y2≤m,
 −1000≤c≤1000,
 −1000≤矩阵内元素的值≤1000
 输入样例：
 3 4 3
 1 2 2 1
 3 2 2 1
 1 1 1 1
 1 1 2 2 1
 1 3 2 3 2
 3 1 3 4 1
 输出样例：
 2 3 4 1
 4 3 4 1
 2 2 2 2
 AC代码：
 
include<iostream>
#include<cstdio>
using namespace std;
const int N=1e3+10;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
  int n,m,q;
  cin>>n>>m>>q;  
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
    cin>>a[i][j];
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          insert(i,j,i,j,a[i][j]);    //构建差分数组
      }
  }
  while(q--)
  {
      int x1,y1,x2,y2,c;
      cin>>x1>>y1>>x2>>y2>>c;
      insert(x1,y1,x2,y2,c);
  }
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
      }
  }
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          printf("%d ",b[i][j]);
      }
      printf("\n");
  }
  return 0;
}
 
如果我的文章对你有帮助，请点点关注，你的关注是对我创作的最大支持。
 
 

 
 
      
      如果你对【前缀和与差分】算法还有疑问的话，欢迎加入我们，一起交流学习！！！  
     
 

 
文章目录
 
说明
完整前缀（138个）
常用前缀

 
说明
 
个人拙见：单词基本上都是由前缀词根后缀然后结合词性组成，所以，只要花大量时间死记硬背的吧前缀词根后缀都背熟以后，结合词性翻译或使用该单词，效率比直接被单词或 通过文章背单词效率高很多。
 
完整前缀（138个）
 
注：下面一个前缀有多重意思的，我都是分开写的，所以你看到有重复的，并不是我搞错了！
 要看使用示例，去看该百度文库中的内容：史上最全英语前缀大全
 
序号
“ - ”表示单词位置
解释
1
a-
加在单词或词根前面, 表示 不，无，非
2
a-
加在单词前, 表示 在…, …的
3
ab-, abs-
加在词根前,表示 相反，变坏，离去 等
4
ab-, ac-, ad-, af-, ag-, an-, ap-, ar-, as-, at-
等加在同辅音字母词根前，表示 一再 等加强意
5
ad-
加在单词或词根前, 表示 做…, 加强…
6
amphi-
表示 两个、两种
7
an-
在词根前, 表示 不，无
8
ana-
表示 错误，在旁边，分开
9
ante-
表示 前面，先
10
anti-
表示 反对，相反
11
apo-
表示 离开，远离
12
auto-
表示 自动、自已
13
be-
构成动词，表示 使…成为
14
be-
构成一些介词
15
bene-
表示 善, 好
16
bi-
表示 二个, 两
17
by-
表示 在旁边，副的
18
cata-
表示 向下，相反，离开
19
circum-
表示 环绕，周围
20
co-
表示 共同 ，通常放元音词根前
21
col-, cor-
在同辅音词根前, 表示 共同
22
com-, con-
表示 共同
23
contra-
表示 反对，相反
24
counter-
表示 反对，相反
25
de-
表示 去掉，变坏，离开，变慢，向下 等
26
de-
表示 使…成为， 加强 等
27
deca-
表示 十
28
deci-
表示 十分之一
29
demi-
表示 半
30
di-
表示 二个，双
31
di-
表示 使…变成，分开，离开
32
dia-
表示 穿过，二者之间
33
dif-
和辅音重复表示 不，否定，分开
34
dis-
表示 不，消失掉
35
dis-
表示 分开，分离
36
dys-
表示 坏，不良
37
e-, ef-
表示 出，出来，
38
em-, en-
表示 进入… 之中，包围
39
em-,en-
表示 使… 进入状态
40
endo-
表示 内部
41
epi-
表示 在…上，在…周围，在…后面
42
eu-
表示 好，优秀
43
ex-
表示 出，出去
44
ex-
表示 前面的，前任的
45
exo-
表示 外部的，外面
46
extra-
表示 以外的，超过的
47
fore-
表示 前面，预先
48
hecto-
表示 百，许多
49
hemi-
表示 半
50
hepta-
表示 七
51
hetero-
表示 异类，异种
52
hexa-
表示 六
53
holo-
表示 全部
54
homo-
表示 同类的
55
hyper-
表示 超过，太多
56
hypo-
表示 下面，次等
57
il-, ir-
辅音重复表示 不，无
58
il-,ir-
表示 使…成为，进入
59
im-, in-
表示 不，无，非
60
im-,in-
表示 向内，进入
61
inter-
表示 在… 之间，相互
62
intra-
表示 在内，内部
63
intro-
表示 向内，入内
64
iso-
表示 等, 同
65
kilo-
表示 一千
66
macro-
表示 宏传， 大
67
mal-; male
表示 坏，恶
68
meta-
表示 超过, 改变
69
micro-
表示 微，小
70
milli-
表示 千，千分之一
71
mini-
表示 小
72
mis-
表示 错误，坏
73
mono-
表示 单个，一个
74
mono-
表示 单个，一个
75
neo-
表示 新的
76
non-
表示 不，非
77
ob-
表示 逆，倒，加强意义
78
octa-
表示 八 ; 亦作octo
79
omni-
表示 全部，到处
80
out-
示 超过，过度
81
out-
表示 出去，过时
82
over-
表示 过度，过份
83
over-
表示 翻转
84
over-
表示 在… 之上
85
paleo-
表示 古，旧
86
pan-
表示 广泛的
87
para-
表示 半，类似，辅助
88
para-
表示 旁边
89
para-
表示 降落伞
90
pen-
表示 近似，差不多
91
penta-
表示 五
92
per-
表示 贯穿，自始至终
93
per-
表示 假，坏
94
peri-
表示 周围，靠近
95
poly-
表示 多
96
post-
表示 在后面
97
post-
表示 邮件，邮政
98
pre-
表示 …前的，预先
99
pro-
表示 赞同，亲…
100
pro-
表示 向前，在前
101
pro-
表示 很多…
102
proto-
表示 原始…
103
pseudo-
表示 假，伪
104
quadri-,quadru-
表示 四
105
quasi-
表示 类似，准
106
re-
表示 向后，相反
107
re-
表示 一再，重新
108
retro-
表示 向后，倒退
109
se-
表示 分开，离开，区别开
110
semi-
表示 半
111
sept-,septi-
表示 七
112
sex-, sexi-
表示 六
113
step-
表示 后，继或前夫(妻)所生
114
stereo-
表示 立体
115
sub-
表示 在下面，次一等，副手
116
sub-
表示 接近，靠近
117
suc-, suf-, sup-, sur-
等辅音重复表示 在…下面
118
super-
表示 在…上面
119
super-
表示 超级，超过，过度
120
supra-
表示 超…
121
sur-
辅音不重复表示 超过，在上面
122
sus-
表示 在… 下面
123
sym-, syn-
表示 共同，相同
124
tetra-
表示 四
125
trans-
表示 横过，越过
126
trans-
表示 变换，改变’；转移
127
tri-
表示 三
128
twi-
表示 二、两
129
ultra-
表示 极端
130
ultra-
表示 超出，超过
131
un-
表示 不，无，非，没有
132
un-
表示 打开，解开，弄出
133
under-
表示 在…下，在…之内
134
under-
表示 不足，不够
135
under-
表示 副手 3
136
uni-
表示 一个、单一
137
vice-
表示 副
138
with-
表示 向后，相反
常用前缀
 
常用个屁，全部前缀也不过才138个，138个前缀都想摸鱼，怎么记成千上万个单词？

一、示例
 
示例 1:
 
输入: ["flower","flow","flight"]
输出: "fl"
 
示例 2:
 
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
 
二、说明
 
所有输入只包含小写字母 a-z 。
 
三、解题思路
 
当字符串数组长度为 0 时则公共前缀为空，直接返回；
令最长公共前缀 ans 的值为第一个字符串，进行初始化；
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀;
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
 
时间复杂度：O(n^2)
 
四、Demo
 
class Solution {
    public static void main(String[] args) {
        String[] strs = new String[]{"flower", "flow", "flight"};
        System.out.println(Solution.longestCommonPrefix(strs));
    }

    public static String longestCommonPrefix(String[] strs) {
        // 判断是否有空字符串
        if (strs.length == 0) {
            return "";
        }
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            // 判断共同前缀是否为空
            if (ans.equals("")) {
                return ans;
            }
        }
        return ans;
    }
}
 
五、图解
 

Description：三体攻击
 
 
 
三体人将对地球发起攻击。
 为了抵御攻击，地球人派出了 A × B × C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第i 层第 j 行第 k 列的战舰（记为战舰 (i, j, k)）的生命值为 d(i, j, k)。三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。
 具体地，第 t 轮攻击用 7 个参数lat, rat, lbt, rbt, lct, rct, ht 描述；所有满足
 i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k) 会受到 ht的伤害。
 如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。
 地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。
 
 
思路1：暴力求解
 
 
 
暴力求解的方法是依次进行每一轮攻击，然后更新攻击范围内的战舰的生命值，当第t轮某一个战舰的血量小于0，那么直接返回 t.
 
 
思路2：二分+差分+前缀和
 
 
 
利用二分，第一次连续攻击m/2轮，然后判断战舰的生命值，如果此时没有战舰爆炸，那么再往后攻击m/4轮；如果此时有战舰爆炸，那么往前恢复m/4轮。不断二分，直到找到是在第几轮攻击时导致战舰爆炸。
 那么怎么实现连续攻击m/2轮？
 利用差分数组，再求前缀和
 
 
一、前缀和的概念：
 
例如，给出一组数 arr[ 1 , 2 , 3 , 4 , 5 ]
 其前缀和 Sn[ 1, 3 , 6 , 10 , 15 ]
 即 Sn[i] = Sn[i-1] + arr[i];
 
二、前缀和的特点：
 
O(N)的时间维护
 例如，arr[2] += 3;
 则Sn[ 1, 3 , 6+3 , 10+3 , 15+3 ]
O(1)的时间获取区间和
 例如，求在 [2,4] 的区间内数值和
 即 Sn[4] - Sn[1] = 15 - 3 = 12
 
三、一维差分数组+前缀和：
 
 
四、二维差分数组+前缀和：
 
 五、三维差分数组+前缀和：
 
 
 
1、三维差分数组
 
 给定三个角的坐标la , ra , lb , rb , lc , rc和攻击力h
 正面四个
 arr[lc][lb][la] += h;
 arr[rc+1][lb][la] -= h;
 arr[lc][lb][ra+1] -= h;
 arr[rc+1][lb][ra+1] += h;
 左面补两个
 arr[lc][rb+1][la] -= h;
 arr[lc][rb+1][ra+1] += h;
 上面再补两个
 arr[rc+1][rb+1][la] += h;
 arr[rc+1][rb+1][ra+1] -= h;
 2、三维前缀和
 
 画的很乱，建议各位自己试着画一画。
 arr[i][j][k] += arr[i][j-1][k]; //后方
 arr[i][j][k] += arr[i-1][j][k];//左侧
 arr[i][j][k] += arr[i][j][k-1]; //下方
 arr[i][j][k] -= arr[i-1][j-1][k]; //左后
 arr[i][j][k] -= arr[i-1][j][k-1]; //左下
 arr[i][j][k] -= arr[i][j-1][k-1]; //后下
 arr[i][j][k] += arr[i-1][j-1][k-1]; //左后下
 
 
六、算法实现
 
暴力求解
 
    private static int[] arr;
    private static int[][] attacks;
    private static int A,B,C,m;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        A = cin.nextInt();
        B = cin.nextInt();
        C = cin.nextInt();
        m = cin.nextInt();
        arr = new int[(A+1)*(B+1)*(C+1)];
        attacks = new int[m+1][7];
        //初始化战舰生命值
        for (int i = 1;i < A+1;i++){
            for (int j = 1;j < B+1;j++){
                for (int k = 1;k < C+1;k++){
                    arr[getIndex(i,j,k)] = cin.nextInt();
                }
            }
        }

        //执行攻击
        for (int k = 1; k < m+1; k++) {
            for (int m = 0;m < 7;m++) //读入攻击信息。
                attacks[k][m] = cin.nextInt();

            for (int i = attacks[k][0];i <= attacks[k][1];i++){
                for (int j = attacks[k][2]; j <= attacks[k][3]; j++) {
                    for (int l = attacks[k][4]; l <= attacks[k][5]; l++) {
                        arr[getIndex(i,j,l)] -= attacks[k][6];
                        if (arr[getIndex(i,j,l)] < 0) {
                            System.out.println();
                            System.out.println(k);
                            return;
                        }
                    }
                }
            }
        }

    }

    static int getIndex(int i, int j, int k){
        return (((i-1)*(B+1)+(j-1))*(C+1)+k);
    }
 
二分+差分+前缀和
 
private static int A, B, C, a, b, c, m;
    private static int[][] attack;//攻击
    private static int[] diff;//差分数组

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        A = cin.nextInt();
        B = cin.nextInt();
        C = cin.nextInt();
        m = cin.nextInt();
        a = A + 1;
        b = B + 1;
        c = C + 1;
        attack = new int[m + 1][7];//m次攻击
        diff = new int[a * b * c];//差分数组(也是战舰生命值数组）

        cin.nextLine();//吃掉换行符
        //战舰生命值初始化(相当于给战舰回血）
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < b; j++) {
                for (int k = 1; k < c; k++) {
                    op(i, i, j, j, k, k, cin.nextInt());
                }
            }
        }

        cin.nextLine();
        //输入每轮攻击范围和强度
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 7; j++) {
                attack[i][j] = cin.nextInt();
            }
            cin.nextLine();
        }

        //二分攻击
        int l = 1, r = m, mid, lastMid = 0;
        while (l < r) {
            mid = (l + r) >> 1;
            if (mid > lastMid) {//说明战舰还没爆炸,需要继续进攻
                for (int i = lastMid + 1; i <= mid; i++)
                    op(attack[i][0], attack[i][1], attack[i][2], attack[i][3], attack[i][4], attack[i][5], -attack[i][6]);
            }
            if (mid < lastMid) {//说明已经有战舰爆炸，需要撤销进攻
                for (int i = mid + 1; i <= lastMid; i++)
                    op(attack[i][0], attack[i][1], attack[i][2], attack[i][3], attack[i][4], attack[i][5], attack[i][6]);
            }
            if (check())
                r = mid;
            else
                l = mid + 1;
            lastMid = mid;
        }

        System.out.println(r);
    }

    static boolean check() {//求前缀和
        int[] temp = new int[a * b * c];
        System.arraycopy(diff, 0, temp, 0, a * b * c);
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < b; j++) {
                for (int k = 1; k < c; k++) {
                    if (j - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i, j - 1, k)];
                    if (k - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i, j, k - 1)];
                    if (i - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i - 1, j, k)];
                    if (i - 1 > 1 && j - 1 > 1)
                        diff[getIndex(i, j, k)] -= diff[getIndex(i - 1, j - 1, k)];
                    if (i - 1 > 1 && k - 1 > 1)
                        diff[getIndex(i, j, k)] -= diff[getIndex(i - 1, j, k - 1)];
                    if (j - 1 > 1 && k - 1 > 1)
                        diff[getIndex(i, j, k)] -= diff[getIndex(i, j - 1, k - 1)];
                    if (i - 1 > 1 && j - 1 > 1 && k - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i - 1, j - 1, k - 1)];

                    if (diff[getIndex(i, j, k)] < 0)//如果当前战舰爆炸了
                        return true;
                }
            }
        }
        return false;//所有战舰都没爆炸
    }

    static int getIndex(int i, int j, int k) {
        return (((i - 1) * (B + 1) + (j - 1)) * (C + 1) + k);
    }

    static void op(int la, int ra, int lb, int rb, int lc, int rc, int m) {
        //正面
        diff[getIndex(la, lb, lc)] += m;
        if (rb + 1 < b)
            diff[getIndex(la, rb + 1, lc)] -= m;
        if (ra + 1 < a)
            diff[getIndex(ra + 1, lb, lc)] -= m;
        if (ra + 1 < a && rb + 1 < b)
            diff[getIndex(ra + 1, rb + 1, lc)] += m;
        //左面
        if (rc + 1 < c)
            diff[getIndex(la, lb, rc + 1)] -= m;
        if (ra + 1 < a && rc + 1 < c)
            diff[getIndex(ra + 1, lb, rc + 1)] += m;
        //上面
        if (ra + 1 < a && rb + 1 < b && rc + 1 < c)
            diff[getIndex(ra + 1, rb + 1, rc + 1)] -= m;
        if (rb + 1 < b && rc + 1 < c)
            diff[getIndex(la, rb + 1, rc + 1)] += m;
    }