前置知识

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

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

前缀和

区间的操作必须拥有逆运算才可用前缀和，所以任意区间的运算结果都可以由两个前缀区间的运算结果逆运算得到，比如 \([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}\)，如图：

\(b\) 的幂次无需快速幂，预处理即可。

差分

前缀计算是可逆的从后往前，将每个元素变成与前一个元素逆运算的结果，差分区间的范围可能比较大，无法将差分点作为数组下标进行索引，差分点的数量与操作数量相关，大部分位置都不是差分点，所以可以将差分点排序，按顺序处理，相同的差分点要合并处理。

高维差分可以将个维度依次进行差分，还原时按照差分相反的顺序逐个维度还原，如二维差分可以看成先差分行在差分列。

前缀和适用于查询较多，差分适用于修改较多。