递推与前缀和

# 算法概述

# 递推的定义

# 递推

通过计算前面的一些项得出序列中指定项的值。

• 斐波拉契数列
• 卡特兰数

# 前缀和

是一种重要的预处理，，能大大降低查询的时间复杂度，可理解为数列的前 n 项和

C++ 中有前缀和的标准库

  
std::partial_sum

# 差分数组

差分是一种和前缀相对的策略，可以当作是求和的逆运算。

• 定义：
  $a_n=b_n-b_{n-1}$
  $a_1=b_1$

• 性质：

1. $a_i$ 的值是 $b_i$ 的前缀和，即$a_n=\sum_{i=1}^n\text{b}_i$
2. 计算 $a_i$ 的前缀和：
   sum = $\sum_{i=1}^na_i = \sum_{i=1}^n\sum_{j=1}^ib_j = \sum_i^n(n-i+1)b_i$

# 递推部分

(例题)

# 前缀和部分

# 一维差分数组

• dif[i] = a[i] - a[i-1]

# 二维差分数组

# 定义

• dif[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

# 前缀和定义：

• pre[i][j] = $\sum_{x=1}^{x_i}\sum_{y=1}^{y_j}a[i][j]$

# 求前缀和：

• pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]

# 算法扩展

# 递推的扩展

# 二阶线性递推式

# OEIS

# 数论

# 前缀和的扩展

# 多维前缀和

# 树上差分

# 边差分