以下方式对数组元素求和的有效方法是什么？

Question

假设给你一个 n 大小的数组 A 和一个整数 k。

现在你必须遵循这个功能：

long long sum(int k)
{
    long long sum = 0;
    for(int i=0; i<n; i++) {
        sum += min(A[i], k);
    }
    return sum;
}

求和最有效的方法是什么？

如果我得到 m(<=100000) 查询，并且每次都给出不同的 k，它会变得非常耗时。

Answer 1

如果查询集随着每个

k

的变化而变化，那么你就不能比 O(n) 做得更好了。优化的唯一选择是使用多个线程（每个线程对数组的某个区域求和）或至少确保编译器正确矢量化您的循环（或使用内在函数手动编写矢量化版本）。

但是如果查询集是固定的并且仅改变

k

，那么您可以通过使用以下优化在 O(log n) 中完成。

预处理数组。对于所有

k

，此操作仅执行一次：

1. 对元素进行排序
2. 制作另一个相同长度的数组，其中包含部分和

例如：

inputArray: 5 1 3 8 7
sortedArray: 1 3 5 7 8
partialSums: 1 4 9 16 24

现在，当给出新的

k

时，您需要执行以下步骤：

1. 对

   k

   中给定的

   sortedArray

   进行二分查找——返回最大元素 <=

   k

的索引
2. 结果是

   partialSums[i] + (partialSums.length - i) * k

Answer 2

你可以做得更好如果你可以对数组进行排序

A[i]

并准备一次辅助数组。

想法是：

• 计算有多少项小于

  k

  ，然后通过公式计算等效总和：

  count*k

• 准备一个辅助数组，它将直接给出优于

  k

  的项目的总和

准备工作

第1步：对数组进行排序

std::sort(begin(A), end(A));

第2步：准备辅助数组

std::vector<long long> p_sums(A.size());
std::partial_sum(rbegin(A), rend(A), begin(p_sums));

查询

long long query(int k) {
  // first skip all items whose value is below k strictly
  auto it = std::lower_bound(begin(A), end(A), k);

  // compute the distance (number of items skipped)
  auto index = std::distance(begin(A), it);

  // do the sum
  long long result = index*k + p_sums[index];
  return result;
}

查询的复杂度为：

O(log(N))

，其中

N

是数组

A

的长度。

准备工作的复杂程度是：

O(N*log(N))

。我们可以使用基数排序到

O(N)

，但我认为这对你的情况没有用。

参考文献

• std::sort()
• std::partial_sum()
• std::lower_bound()

Answer 3

你所做的看起来绝对没问题。除非这确实是绝对时间关键的（即客户抱怨你的应用程序太慢并且你测量了它，而这个函数就是问题所在，在这种情况下你可以尝试一些不可移植的向量指令，例如）。

通常，你可以通过从更高的层次来看待事情来更有效地做事。例如，如果我写

for (n = 0; n < 1000000; ++n)
   printf ("%lld\n", sum (100));

那么这将需要很长的时间（五万亿的添加）并且可以更快地完成。如果一次更改数组 A 的一个元素并每次都重新计算总和，则效果相同。

Answer 4

假设数组 A 有 x 个不大于 k 的元素，集合 B 包含大于 k 且属于 A 的元素。

则函数 sum(k) 的结果等于

k * x + sum_b

，其中 sum_b 是属于 B 的元素之和。

可以先对数组A进行排序，然后计算数组pre_A，其中

pre_A[i] = pre_A[i - 1] + A[i] (i > 0),
        or 0 (i = 0);

然后对于每个查询k，在A上使用二分查找找到不大于k的最大元素u。假设u的索引为index_u，则sum(k)等于

 k * index_u + pre_A[n] - pre_A[index_u]

。每个查询的时间复杂度是 log(n)。

如果数组A可能会动态变化，可以使用BST来处理。