前缀和 / 差分

yhylivedream · 2024-02-27 23:17:36 · 算法·理论

前置知识

有某些运算拥有逆运算，通过逆运算，可以撤销原运算的效果。

比如：加法和减法互为逆运算、乘法和除法互为逆运算、 异或的逆运算就是自身、求最大值、最小值不具有逆运算、修改不具有逆运算。

前缀和

区间的操作必须拥有逆运算才可用前缀和，所以任意区间的运算结果都可以由两个前缀区间的运算结果逆运算得到，比如 [x,y]=[0,y]-[0,x-1]，注意 x=1 时若下标从 0 开始会越界，所以一般下标从 1 开始，用 string 是要小心。

发现每次计算前缀区间时间很浪费，所以预处理所有前缀区间的运算结果。

进制区间

给定长为 n 的数列 a_i 与基数 b，进行 t 次询问，每次询问 [l, r] 内元素作为 b 进制表示时的数值，对 10^9+7 取模的结果。

分析

预处理每个前缀的 b 进制数为 s 数组，s_i=s_{i-1}\times b + a_i，对于每次 [i,j]，先将两个前缀区间取出，需要将 [0,i-1] 这段区间偏移 b^{j-i+1}，如图：