前缀和与差分

0X00 一维前缀和

n, m = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0] * (n+1)

for i in range(1, n+1):
    sums[i] = sums[i-1] + nums[i-1]
    
for _ in range(m):
    n1, n2 = map(int, input().split())
    print(sums[n2] - sums[n1-1])

0X01 二维前缀和

n, m = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0] * (n+1)

for i in range(1, n+1):
    sums[i] = sums[i-1] + nums[i-1]
    
for _ in range(m):
    n1, n2 = map(int, input().split())
    print(sums[n2] - sums[n1-1])

0X02 一维差分

一维差分推导：

假设我们有数组 a 现在构造一个数组 b 使得： 那么 b 的前 n 项和就是 并且如果我们向 增加一个数 c 那么再求 到 的时候都会加上一个 c。因此我们完成了在 的时间给一段数加上某一个数

现在我们来写它的模板：

差分只有一个操作 add，就是给一段区间加上一个值，

def add(l, r, v):
    b[r+1] -= v
    b[l] += v

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n+1)

def add(l, r, v):
    b[r+1] -= v
    b[l] += v

for i, v in enumerate(a):
    add(i, i, v)

# print(b)
while q > 0:
    q -= 1
    l, r, v = map(int, input().split())
    add(l-1, r-1, v)

0X03 二维差分

构造一个二维数组 b 使得 b 的二维前缀和是 a

同样只有一个操作记住下面这张图：

想要绿色部分的 a 在 o(1) 的时间内全部加上 c 则只需要在 b 的图中 +c 的位置 +c -c 的位置 -c。就可以了

def add(x1,y1, x2, y2, v):
  b[x1][y1] += v
  b[x2+1][y1] -= v
  b[x1][y2+1] -= v
  b[x2+1][y2+1] += v