一道简单的“求和”算法题

昨天某个同学询问了我一道算法题,题目如下:

给你一个长度为 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],按照“前缀和”的套路,则有:

数组以 0 为下标,第一个元素为 a[0]

而正确答案应该是:

似乎不太一样,可是别急,我们把这两个式子相减,那么就会有:

wow,好像正好是“前缀和”的一个倍数关系(left-1倍)!那么就很简单了,我们令数组 g 来记录传统的“前缀和”,即:

所以,对于每一次查询 left 到 right,我们就可以用这两个数组直接算出来:

这样,我们只需要在读取数组时,顺便完成 f 和 g 这两个数组的初始化工作,初始化时只需要一边读取数组一边根据上一个元素的结果递推出来,所以复杂度没有增加。

在询问时,只需要根据 f 和 g 这两个预计算的数组,直接根据计算出来,每次询问的时间复杂度降到了 O(1)。

有任何想法?请发邮件告诉老夫:daozhihun@outlook.com