前缀 差分

作者： 作者的头像   月弦音 ,  2023-12-09 00:14:14 ,  所有人可见 ,  阅读 102

0


1

前缀和

S[ j ],即对a[ i ]的前j项和不断进行相加
通过递推求出的基本信息之一
a[ i ]的某个区间内的和，也可以用前缀和相减求出

差分

前缀和，与差分互为逆运算
前缀和的差分序列即原序列

为什么要使用差分序列

如果想对一个区间整体进行+1，-1运算，可以优化为仅对差分序列两个单点进行运算
一个元素+1，一个元素-1

区间运算——>两个点运算

``

0 评论

1024
x