前缀和 & 差分

前缀和与差分是常用的区间优化方式，其中前缀和数组可以将区间查询的时间复杂度降为常数，而差分数组则可以将区间修改的时间复杂度降为常数。

一、前缀和

前缀和知识点简单易理解，但出题难度较大，需要根据题意挖掘出潜在的前缀和关系，建立辅助数组求解问题。

（1）一维前缀和

定义：

对数组 $x_0,x_1,x_2,...,x_n$，对其进行区间查询的时间复杂度是 $O(n)$ 为了提高区间查询的效率，可以引入前缀和数组 $y_0,y_1,...y_n$，前缀和数组有以下定义：
$$\begin{gathered} y_0=x_0 \\ {y}_1=x_0+x_1 \\ {y}_2=x_0+x_1+x_2... \end{gathered}$$

创建方式：

由定义可知，前缀和数组有递推生成公式：$y_i=y_{i-1}+x_i(i>0)$这个公式是生成前缀和数组的主要方式。

应用方式：

在创建前缀和数组以后，如果要查询原数组在区间[a,b]上的元素和，只需要使用公式 $y_b-y_{a-1}$ 即可在 $O(1)$ 的时间复杂度上求出区间元素和。

例题 1：和与乘积（蓝桥杯第12届国赛真题）

题目描述：

给定一个数列 $A=(a_1,a_2,...,a_n)$，问有多少个区间 $[L,R]$ 满足区间内所有元素的和等于区间内所有元素的乘积。

输入格式：

输入第一行包含一个整数n。第二行包含n个整数，依次表示数列 $a_1,a_2,...,a_n$

输出格式：

输出仅一行，包含一个整数表示满足如上条件的区间的个数。

提示：

$1\le n\le 200000,1\le a_i\le 200000$。

代码示例：

# 自己写的粗糙前缀和代码，超时了
n = int(input())
a = [int(i) for i in input().split()]
# 创建前缀和数组
b = [0]*n
b[0] = a[0]
for i in range(1, n):
    b[i] = b[i-1] + a[i]
# 利用滑动窗口求出区间乘积
ans = 0
# 区间长度
for l in range(1,n+1):
    temp = 1
    for right in range(n):
        if right < l-1:
            temp *= a[right]
        elif right == l-1:
            # begin to judge 
            temp *= a[right]
            if temp == b[right]:
                ans += 1
        else:
            temp *= a[right]
            temp //= a[right-l]
            if temp == b[right] - b[right-l]:
                ans += 1
print(ans)

# 观察规律，进行剪枝
# 注意到数组中1的特殊作用，正是有了1才让元素之和的增长速度有可能追上元素之积
# 类比前缀和的思想，使用多个数组存储原数组的各种信息
# input
n = int(input())
a = [int(i) for i in input().split()]

# initialize
# 创建数组num[]，存储原数组中所有的非1元素，注意非1元素之间的相对顺序不变
num = []
# 创建数组one_cnt[]，one_cnt[i]存储num[i]在原数组中前面连续的1的个数
one_cnt = []

# 填充这几个辅助数组
cnt = 0 # 记录当前非1元素前缀1的个数
for i in range(n):
    if a[i] == 1:
        cnt += 1
    else:
        # 每遇到一个非1元素，就存储该元素前连续1的个数，然后清零重新计数
        one_cnt.append(cnt)
        cnt = 0
        num.append(a[i])
if one_cnt:
    # 注意还要将最后一个非1元素右边的连续1的个数也记录下来
    one_cnt.append(cnt)
# 填充add数组
# 创建前缀和数组add[]，add[i]是num[i]在原数组中的前缀和（包含它以及它以前所有元素的和）
add = [0]*len(num)
for i in range(len(num)):
    if i == 0:
        add[0] = one_cnt[0] + num[0]
    else:
        add[i] = add[i-1] + one_cnt[i] + num[i]
# 开始正式求解
ans = n # 每一个长度为1的区间都符合题意，一共有n个
# 整个原数组的元素和
all_sum = add[-1] + one_cnt[-1]
# 遍历非1数组num
for left in range(len(num)-1):
    # create a variable to record the multiple result of all of the elements in the interval
    m = num[left]
    # 对left = 0特别处理
    if left == 0:
        for r in range(left+1,len(num)):
            m *= num[r]
            if m > all_sum:
                break
            diff = m - (add[r] - one_cnt[left])
            if diff > 0:
                if diff <= one_cnt[r+1] + one_cnt[left]:
                    # 这里的ll和rr记录了左右两侧最多能够取多少个1到当前的子序列中
                    # 相当于求一个长度为diff的滑块在长度为ll+rr的滑槽中滑动的位置数
                    # 受限于滑块本身的长度，部分坐标（共diff-1个)是取不到的，所以减去
                    ll = min(diff,one_cnt[left])
                    rr = min(diff,one_cnt[r+1])
                    ans += ll+rr-diff+1
            elif diff == 0:
                ans += 1
        continue

    for right in range(left+1,len(num)):
        # because the 1 will not change the result of multiple,so ignore them
        m *= num[right]
        if m > all_sum:
            # 乘积超过总和，直接排除
            break
        # 再看乘积与区间和的差值
        d = m - (add[right] - add[left-1] - one_cnt[left])
        if d > 0:
            # 尝试用左右两侧的1补齐
            if d <= one_cnt[right+1]+one_cnt[left]:
                # 可以补全
                # 但因为1有多种取法，所以有多种情况
                # ans += min()+1 + min()+1 - (d+1)
                l_case = min(d,one_cnt[left])
                r_case = min(d,one_cnt[right+1])
                ans += l_case+r_case-d+1
        elif d == 0:
            ans += 1
print(ans)

例题 2：字串简写（蓝桥杯第14届省赛真题）

题目描述：

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。
给定一个字符串 S 和两个字符 $c_1$ 和 $c_2$，请你计算 $S$ 有多少个以 $c_1$ 开头 $c_2$ 结尾的字串可以使用这种简写。

输入格式：

第一行包含一个整数 $K$，第二行包含一个字符串 $S$ 和两个字符 $c_1$ 和 $c_2$。

输出格式：

输出一个整数表示答案。

代码示例：

# 可以直接暴力，但肯定会超时，这种题目评测数据很大，纯暴力拿不了几分
k = int(input())
s,c1,c2 = input().split()
# 创建两个辅助数组，存储字符串中c1和c2字符的下标
begin = []
end = [] 
for i in range(len(s)):
    if s[i] == c1:
        begin.append(i)
    if s[i] == c2:
        end.append(i)
# 两重for循环判断每一对c1和c2是否符合题意
ans = 0
b = len(begin)
e = len(end)
startIndex = 0
for i in range(b):
    for j in range(startIndex, len(e)):
        # 如果不满足题意，直接跳过
        if end[j]-begin[i]+1 < k:
            continue
        # 满足题意，直接利用end[]数组的长度计算出后续还有多少个符合条件的c2
        ans += e - j
        # 更新startIndex，下一次从j开始搜索，因为 begin[i+1] > begin[i]
        startIndex = j
        # 直接结束本轮搜索
        break
print(ans)

例题 3：灵能传输

解题思路:

对三个相邻的数 $a_{i-1},a_i,a_{i+1}$，无论 $a_i<0$ 还是 $a_i>0$ 都可以进行操作将其变为 $a_{i-1}+a_i,-a_i,a_{i+1}+a_i$，注意到修改操作不会改变除这三个元素的序号以外的前缀和数组，而对前缀和数组来说，这个操作相当于互换了 $b_{i-1}$ 和 $b_i$ 的值。

（2）二维前缀和

二维前缀和出题特征明显，往往会直接指出需要进行二维区间查询操作，但不需要进行二维区间修改。对二维前缀和的求解和应用基本上是围绕容斥定理进行的。

例题 1：P1387 最大正方形

题目描述：

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

输入格式:

输入文件第一行为两个整数 $n,m(1\le n,m\le 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

输出格式:

一个整数，最大正方形的边长。

def init(c):
    return int(c)^1

def check(l):
    if l == 0:
        return True
    global n,m,matrix, add
    # 检查是否存在符合题意的边长为l的正方形区间
    for i in range(n-l+1):
        for j in range(m-l+1):
            # 计算区间和是否为0
            temp = add[i+l-1][j+l-1]
            if i > 0 and j > 0:
                temp = temp - add[i+l-1][j-1] - add[i-1][j+l-1] + add[i-1][j-1]
            elif i > 0 and j == 0:
                temp = temp - add[i-1][j+l-1]
            elif i == 0 and j > 0:
                temp = temp - add[i+l-1][j-1]
            if temp == 0:
                return True
    return False

n,m = map(int,input().split())
matrix = []
for i in range(n):
    matrix.append([init(j) for j in input().split()])
# 初始化二维前缀和数组
add = [[0]*m for i in range(n)]
for i in range(m):
    add[0][i] = matrix[0][i]
for i in range(1,n):
    add[i][0] = matrix[i][0]
for i in range(1,n):
    for j in range(1,m):
        add[i][j] = matrix[i][j] + add[i-1][j] + add[i][j-1] - add[i-1][j-1]
# 二分法搜索区间和为0的最大正方形区间
left = 0
right = min(n,m)
while left < right:
    mid = (left+right+1)//2
    if check(mid):
        left = mid
    else:
        right = mid-1
print(right)

二、差分

差分是一种和前缀和类似的概念，二者都通过构建辅助数组存储原数组的信息，从而简化计算过程，提高效率。不同的是，差分数组用于记录原数组中相邻两个元素的差值。
差分数组的作用：

将区间修改的时间复杂度从线性级降低为常数级，但用差分数组实现的单点查询操作时间复杂度为线性，所以差分数组主要用于需要多次区间修改后读取数值的情景。

差分数组的创建方式：

$b_i=\{\begin{array}{ll}{a}_i-a_{i-1}& i\in [2,n]\\ a_1& i=1\end{array}$

差分数组的读取方式：

差分数组的前缀和数组就是原数组，所以在差分数组中进行单点读取的时间复杂度是线性的。

例题 1：棋盘（蓝桥杯第14届省赛真题）

题目描述：

小蓝拥有一个 n×n 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反（也就是白色棋子变为黑色，黑色棋子变为白色）。请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式：

输入的第一行包含两个整数 $n,m$ 用一个空格分隔，分别表示棋盘的大小和操作数。接下来 m 行每行包含四个整数 $x_1,y_1,x_2,y_2$ ，四个数用空格隔开，表示将 $x_1$行 和 $x_2$行与 $y_1$列 和 $y_2$列之间的所有棋子取反。

输出格式：

输出 n 行，每行 n 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0，否则输出 1。

代码示例：

# 差分
# 偶数表示棋子是白色，奇数表示棋子是黑色
# 初始值为0

n,m = map(int,input().split())
# initialize the board
# b是一个棋盘的差分数组
b = [[0]*(n+2) for i in range(n+2)]
# begin to run the instructions
# 每一条指令都让区间内所有元素加一，最后看元素的奇偶性决定最终的棋子状态
for _ in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    b[x1][y1] += 1
    b[x2+1][y1] -= 1
    b[x1][y2+1] -= 1
    b[x2+1][y2+1] += 1
# 还原原数组，计算出结果
a = [[0]*(n+2) for i in range(n+2)]
for i in range(1,n+1):
    for j in range(1,n+1):
        a[i][j] = (a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j]+2)%2
        print(a[i][j],end = '')
    print()

例题 2：三体攻击

题目链接：三体攻击（蓝桥杯）

题目描述：

三体人将对地球发起攻击。为了抵御攻击，地球人派出了 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 的伤害。
如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。
地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

输入描述：

第一行包括 4 个正整数 A,B,C,m；第二行包含 A×B×C 个整数，其中第 ((i−1)×B+(j−1))×C+(k−1)+1 个数为 d(i, j, k)；
第 3 到第 m+2 行中，第 (t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。

输出格式：

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

代码示例：

# 二分法+三维差分
# 可以通过 75% 的测试样例，剩余 25% 超时
# 本题需要使用多次单点查询，由于战舰爆炸与否具有二分特性，所以可以使用二分法确定首个战舰爆炸的时刻
# 使用三维差分数组提高区间修改的效率

def check(times):
    # 检查经过times轮的攻击后是否存在爆炸的战舰、
    global a,b,c,hits
    reduce = [[[0 for i in range(c+2)] for j in range(b+2)] for k in range(a+2)]
    for t in range(times):
        la,ra,lb,rb,lc,rc,v = hits[t]
        reduce[la][lb][lc] += v
        reduce[la][lb][rc+1] -= v
        reduce[la][rb+1][lc] -= v
        reduce[ra+1][lb][lc] -= v
        reduce[ra+1][rb+1][lc] += v
        reduce[ra+1][lb][rc+1] += v
        reduce[la][rb+1][rc+1] += v
        reduce[ra+1][rb+1][rc+1] -= v
    # 根据差分数组还原出原数组，并和防御值进行比较
    # 注意原坐标从1开始计数
    for i in range(1,a+1):
        for j in range(1,b+1):
            for k in range(1,c+1):
                # 将差分数组转换成其所对应的前缀和数组
                # 容斥定理
                reduce[i][j][k] += reduce[i-1][j][k]+reduce[i][j-1][k]+reduce[i][j][k-1]-reduce[i-1][j-1][k]-reduce[i-1][j][k-1]-reduce[i][j-1][k-1]+reduce[i-1][j-1][k-1]
                # 检查是否爆炸
                if reduce[i][j][k] > d[(k-1)+c*((j-1)+b*(i-1))]:
                    return True
    return False

a,b,c,m = map(int,input().split())
d = [int(i) for i in input().split()]
hits = [list(map(int,input().split())) for i in range(m)]
# binary search
left = 1
right = m
while left < right:
    mid = (left+right)//2
    if check(mid):
        right = mid
    else:
        left = mid+1
print(left)