基础算法——前缀和与差分

1       前缀和>      前缀和>
    b[i]        a[i]        s[i]
        <差分        <差分

2   范围
    [1,n]
    其他为0

3   前缀和([l,r]内所有数的和)
    s[i]=s[i-1]+a[i]
    sum(l,r)=s[r]-s[l-1]

4   差分([l,r]内所有数同时+-d)
    b[1]=a[1]
    b[i]=a[i]-a[i-1]

    a(l,r)+d=b[l]+d
             b[r+1]-d
    只需b[2~n]为0，a[n]就不变
    调整b[1]可使整条a[n]变化

5   矩阵前缀和
    s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1]
    (x1,y1)(x2,y2)为左上右下矩阵和
    =s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

6   矩阵差分
    把原数组看成全是0
    (x1,y1)(x2,y2)为左上右下矩阵+d
    b[x1][y1] + d;
    b[x2 + 1][y1] - d;
    b[x1][y2 + 1] - d;
    b[x2 + 1][y2 + 1] + d;