个人使用代码模板（Python3版本）

1、一维前缀和

s[i] = a[1] + a[2] + a[3] + … + a[i]
a[l] + … + a[r] = s[r] - s[l-1]

2、二维前缀和

s[x][y]记录当前位置（x,y）距离起始点的距离

例题：AcWing 5590. 沿栅栏散步

def get(x, tx):
    # 判断到下一个点往哪里移动
    if tx > x:
        return 1
    if tx < x:
        return -1
    return 0

p_sum = 0
x = ppoint[p-1][0]
y = ppoint[p-1][1]  # 将最后一个点作为起始点
s = [[0]*1001 for _ in range(1001)]
for i in range(p):
    tx = ppoint[i][0]
    ty = ppoint[i][1]
    vx = get(x, tx)
    vy = get(y, ty)
    while(x!=tx or y!=ty):  # 从(x,y)移动到(tx,ty)
        x += vx
        y += vy
        p_sum += 1
        s[x][y] = p_sum  # 记录当前距离原点的距离

更新中…