ksm快速幂算法

差分数组

差分数组的作用是用于频繁的对某个区间的数组进行加减。比如说，我给你输入一个数组 nums，然后又要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减 3，再给 nums[0..4] 全部加 2，再给…。一通操作猛如虎，然后问你，最后 nums 数组的值是什么？

差分数组如何构造

vector<int> nums;
int n = nums.size();

vector<int> diff(n);
diff[0] = nums[0];
for (int i = 1; i < n; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

通过这个差分数组是可以反推出原来的数组的，比如我们想要得到nums：

vector<int> nums(n);
nums[0] = diff[0];
for (int i = 1; i < n; i++) {
    nums[i] = nums[i - 1] + diff[i];
}

如何对某个区间的值进行加减操作呢？如果你想对[i, j]区间的值加x，只需将diff[i]加x，将diff[j + 1]减x即可。这样在反推出原数组的时候，就会发现[i, j]区间的值都加上了x。

void update(vector<int>& diff, int i, int j, int x) {
    diff[i] += x;
    if (j + 1 < diff.size()) { // 注意边界，当区间碰到数组末尾时，不用减
        diff[j + 1] -= x;
    }
}