E - Mod Sigma Problem——atcoder378

E - Mod Sigma Problem

看到这道题的第一眼，我觉得它应该是要用前缀和来做。但是如果这样来求区间和的话，就需要做一个嵌套循环，一层循环遍历左边界，一层循环遍历右边界，时间复杂度为O(n2)。在N的最大值为2 * 105的情况下，这个复杂度是难以接受的，怎样找到一个线性复杂度的算法来处理这个问题？

我请教了主打算法竞赛的室友，他提出这道题可以用树状数组来做。好家伙，这是一个我完全陌生的数据结构，感觉很高大上的样子。经过他的讲解，以及我对正确代码的阅读，我现在已经理解了这道题的思路，同时领悟了树状数组的巧妙之处。

首先，对题目进行分析，对给出的式子用前缀和的方式化简。最后得到这样的形式

if (preSum[r]%m - preSum[l - 1]%m) {
	result += preSum[r]%m - preSum[l - 1]%m + m;
} else {
	result += preSum[r]%m - preSum[l - 1]%m;
}

观察发现，两种情况的区别只在于，前者需要额外加上一个m。那么对于任意给定的右边界，他对最终结果的贡献其实就可以划分为三部分，一部分为(preSum[r]%m) * r，一部分为前面所有前缀和之和sum，最后一部分为m乘以它的个数，也就是在这里就需要用到树状数组，树状数组中保存信息是小于当前下标的模值的个数。

总结反思

• 之后做题的时候可以尝试对问题变形化简，降低问题的复杂度，然后再看需要什么信息，这个信息适合用什么数据结构或算法来存储获取。
• 迷惑点1：为什么需要建立长度为m + 1大小的树状数组而不是m？这是因为树状数组是利用了数字二进制位的信息，而只有从1开始才具有这样的性质，通常从零开始是没有这种性质的。也因为这个原因，如果要把本来是从零开始的信息存储到树状数组中，需要做一个简单的映射，也就是需要整体下标向右偏移一位，例如原本应存储在下标0的元素现在需要映射到1，相应地，查询的时候也需要+1再查询。
• 迷惑点2：树状数组中保存的是什么信息？保存的是小于当前下标值的模值的个数。
• 迷惑点3：怎么一步步把原始的信息处理成所需的信息的？首先，根据简化后的运算公式，并不需要原始的前缀和信息，只需要模值做相应的运算，而模值的规模局限在0~m-1的范围内，并且每个模值正好可以映射到下标上，这样就只需要在每次读取一个数时，计算最新的模值，并更新树状数组中该模值的个数，以及包含了该模值个数的父节点的值，读取的时候就只需要以该模值做参数查询即可。
• 要想清楚真正需要的是什么信息，不需要的信息可以不用理会，在处理的过程中完全可以允许丢失，这样可以降低大量的复杂度。