如何快速地向矢量中的一系列元素添加数字

Question

如何在向量中添加一个常量qazxsw poi到一系列元素qazxsw poi，真快！我编写的代码适用于k查询数量相对较短的输入：

[a,b]

但这显然是一个非常缓慢的解决方案！对于较大的k值和范围，代码需要更长的时间，例如q和

    long int a,b,k,n;
    vector<long int> v(n+1,0);
    for( long int i=0; i<q ;i++)
       {
          cin>>a>>b>>k;
          for(int j=a-1; j<=b-1; j++)
             {
               v[j]+=k;
             }
       }

将花费更长的计算时间。那么是否有更快的方式以更短的时间完成工作？

编辑：我的方法为更大数量的查询（10 ^ 7）和范围达到10 ^ 7的数量时给出超时。

Answer 1

据我所知，你有[a,b]=6581237, 9872072查询，并且对于每个查询，你需要为一个数组范围内的每个元素添加一个数字。这就解释了为什么你认为在具有几百万个元素的向量上这样做会花费太长时间，因为这样做只需要不到一秒钟。

你需要的是一个k=87106，或一个带有延迟传播的Q，它允许你更新一系列元素或以对数时间查询元素的值。段树还可以以对数时间执行范围查询。

Fenwick树本身可以执行点更新和前缀和查询，但我们可以使用以下内容进行范围更新和点查询：

Fenwick tree

对于分段树解决方案，您将需要segment tree来执行范围更新。

我认为如果您是第一次学习维基百科页面可能会有点混乱，所以这里有一些来自hackerearth.com的教程：

• 芬威克树：

  //Add val to every element in [left, right]:
  update(left, val);
  update(right + 1, -val);
  
  //Query the value at index x:
  query(x);

• 细分树：lazy propagation

Answer 2

你有/期望多少重叠的间隔？

如果范围非常大，则它们确实存在重叠的可能性。对于所有这些重叠，您可以多次计算加法。想象一下以下情况：

[10; 100] + 20
[30;  50] - 10
[40; 120] + 10

您可以解决重叠，使每个元素只有一个添加（当然，您需要在进行任何计算之前查询范围，然后将它们存储在一些适当的数据结构中）：

[ 10;  30] + 20
[ 30;  40] + 10
[ 40;  50] + 20
[ 50; 100] + 30
[100; 120] + 10

由于现在具有独立范围，您可以另外并行化添加（例如，通过将范围放在队列中并让每个线程在完成其前一个线程后立即从中获取一个 - 队列需要受到针对竞争条件的保护）。