昨天某个同学询问了我一道算法题，题目如下：
给你一个长度为 n 的整数序列 a ，对该序列有 q 个查询，每次询问涉及序列中从 left 到 right 之间的数，包 括 left 和 right ，请给出公式：
的结果。即输出 [left, right] 这段区间中，第一个数乘以 1 ，第二个数乘以 2 ，第三个数乘以 3 ，……的 和。
整数序列的长度不超过 10^5，每个数都在 [0, 10^5] 之间。
对于每个序列，一共有 q 次查询（q <= 10^5），每次查询的结果返回如题目所述：为 left 到 right 区间内，第一个数乘以 1，第二个数字乘以 2，第三个数字乘以 3 …… 的和。
(Thinking….)
(Thinking….)
(Thinking….)
每个查询如果直接去算的话，需要计算 right – left + 1 个数字，时间复杂度就是 O(n)，对于 q 次查询，复杂度就是 O(n*q)。由于查询数量很多，对于 10^5 这个数量级的话，每次查询至少也得 O(log n) 的复杂度才行。
刚看到这个题目，老夫的第一反应就是“前缀和”，但由于返回结果与左边界有直接关系，那么直接使用貌似是不行的。但经过尝试，发现似乎可行：
类似于前缀和，我们令数组 f 中的元素为（数组以 0 为起始下标，所以第 i 个元素要乘以 i+1）：
那么对于查询 [3, 5]，按照“前缀和”的套路，则有：
而正确答案应该是：
似乎不太一样，可是别急，我们把这两个式子相减，那么就会有：
wow，好像正好是“前缀和”的一个倍数关系（left-1倍）！那么就很简单了，我们令数组 g 来记录传统的“前缀和”，即：
所以，对于每一次查询 left 到 right，我们就可以用这两个数组直接算出来：
这样，我们只需要在读取数组时，顺便完成 f 和 g 这两个数组的初始化工作，初始化时只需要一边读取数组一边根据上一个元素的结果递推出来，所以复杂度没有增加。
在询问时，只需要根据 f 和 g 这两个预计算的数组，直接根据公式计算出来，每次询问的时间复杂度降到了 O(1)，空间复杂度则为 O(n)。PS：如果每次询问直接硬算，乃也需要保存输入的数组，所以空间复杂度没有增加。