时间复杂度

时间复杂度，就是电脑运行一段程序所需要的时间。

另外，电脑每秒可以运行1e8次。($x$ e $y$代表$x$乘10的$y$次方，即100000000次)

时间复杂度记作 $O(n)$。

普通的时间复杂度(常数时间)记作 $O(1)$，为一段最简单的程序的时间复杂度。

如以下程序的时间复杂度为 $O(1)$：

#include <stdio.h>
using namespace std ;

int main()
{
    int n ;
    
    return 0 ;
}

没错，什么都没有干，只创建了一个变量。

开始

前缀和是一种优化算法，用于求区间和。若数据范围特别大，写 for 循环很可能会爆时间复杂度，就可以用上前缀和了。前缀和有一维前缀和和二维前缀和，我暂时还没有学二位前缀和，故在此不多赘述。

使用

一维前缀和需要把一个数组比如数组 $a[1]$ 到 $a[n]$ （$n$ 为 $a$ 数组长度）储存到另一个数组中比如 数组 $b$。那么：

b[i] \ (i \le n) = \displaystyle\sum_{j = 1}^{i} a[j]

C++命名空间的概念

在同一个作用域中，不同的数据不能起同一个名字，但是C++命名空间概念的出现，提供了解决问题的方案。在不同的命名空间中，可以随意定义相同的名字。命名空间就是为了避免你包含的头文件中与你自己定义的任意类，数据，函数重名，造成令人迷惑的错误而产生的。

函数的作用

一般来说，我都是懂的。函数的总用比较简单：

1. 优化代码量
2. 让程序代码更加清晰明了
3. 调用时更加方便

总之，函数的存在就是为了更加方便，清晰，快速。

什么是差分，差分与前缀和的关系

差分也是一种优化算法。同时，差分是前缀和的逆运算，也就是说，前缀和也是差分的逆运算。因此，由前缀和数组可以求出差分数组，由差分数组也可以求出前缀和数组。

假设数组 $a$ 是原数组，数组 $b$ 是差分数组，则：$b_i = a_i - a_{i-1}$

差分可以用于修改数组的操作。因为假设我需要将 $a_2$ $a_3$ $a_4$ 都加上 $2$ ，此时若使用前缀和则需要再使用递推重新求一遍前缀和，非常耗时。这时便可以使用差分数组。可以发现：

\underbrace{b_1,\hspace{2mm} b_2}_{b_2 + 2 = b_1} ,\hspace{2mm} b_3,\hspace{2mm} \overbrace{b_4,\hspace{2mm} b_5}^{b_5 - 2 =b_4}

因此，只需修改差分数组中的两个项，然后再通过前缀和是差分的逆运算，即可求出原数组，从而完成数组的修改。