二分的意义

优化。顾名思义，将一整个有序的数列分成两个部分，不断缩小边界，查找某个数字。
二分的时间复杂度为 $O(log\ 2\ n)$ 。

此时，我们学的还是整数二分以及浮点二分。

整数二分的两个模板

二分的前提是这个序列是有序的，也就是单调递增的。
一般来说，二分会取中间值进行初始化，再判断这个中间值是否大于目标值。若是，则缩减左边界，否则缩减右边界。直至逼近答案。
说“逼近”，是因为有时查找的元素不存在于序列中，那所二分出的答案是接近于的，但又是不正确的。所以要加上一个特判。除非说明给出的想查询的元素所有都是存在于序列中的。

指针的作用

指针，顾名思义，就是指向某一东西的标志。

当我们想存地址时，就可以使用指针变量：

int a ;
int *b = &a ;

b就是一个指针变量，存着a的地址。

宏定义和类型定义

宏定义，将一个指令导向另一个指令。宏定义属于预处理指令，使用规范为：

#define [标识符] [常量]

时间复杂度

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

另外，电脑每秒可以运行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]