c++ - 如何在 C++ 中增加 vector 中 k 个连续元素的值？

Question

假设我们在 c++ 中有一个大小为 8 的 vector ，其中包含元素 {0, 1, 1, 0, 0, 0, 1, 1} 并且我想将 vector 的特定部分的大小增加一个，例如，假设vector需要增加1的部分是0到5，那么我们最终的结果是{1, 2, 2, 1, 1, 0, 0, 1, 1}。

是否可以使用标准的 vector 方法(就像我们在 c 中的 memset)在恒定时间内执行此操作，而无需运行任何循环？

Answer 1

不...顺便说一句，memset 也不能保证恒定时间操作(在大多数实现中速度非常快，但在元素数量上仍然是线性的)。

如果你需要在一个非常大的 vector 上多次执行这种操作(在一个范围内加/减一个常量)并且你需要获得最终结果，那么每次更新你可以得到 O(1)使用不同的算法:

第 1 步:将数据转换为其“导数”

这意味着用与前一个元素的不同替换每个元素。

// O(n) on the size of the vector, but done only once
for (int n=v.size()-1; i>0; i--) {
    v[i] -= v[i-1];
}

第 2 步:执行所有间隔操作(每个操作都在恒定时间内)

使用这种表示法，将常量添加到范围仅意味着将其添加到第一个元素并从结束元素之后的元素中减去它。在代码中:

// intervals contains structures with start/stop/value fields
// Operation is O(n) on the **number of intervals**, and does
// not depend on the size of them
for (auto r : intervals) {
    v[r.start] += r.value;
    v[r.stop+1] -= r.value;
}

第 3 步:收集结果

最后只需取消初始处理，通过积分恢复到每个单元格上的正常值。在代码中:

// O(n) on the size of vector, but done only once
for (int i=1,n=v.size(); i<n; i++) {
    v[i] += v[i-1];
}

请注意，如果尺寸足够大，步骤 1 和步骤 3(推导和集成)都可以在 N 个内核上以完美的效率并行完成，即使乍一看可能并不明显(这是至少对我来说是这样)。