how to add increasingly more to an array-CodePudding

Is there a way to have Q different updates of the following kind:

v[start] = v[start]   1;
v[start   1] = v[start   1]   2;
v[start   2] = v[start   2]   3

and so on.. to the position end

v[end] = v[end]   end - start   1

in O(N Q)?
I mean something like difference arrays. Can you please help me?
If it helps, the array is initially only 0s.
Clarification:
N = array size
Q = Number of updates
All the updates have different starting and ending indices and I do not need to access any element of the array in between the updates. I only need them after i performed each update.

CodePudding user response：

Oops, I read the problem as

v[start] = v[start]   1;
v[start   1] = v[start]   2;
v[start   2] = v[start   1]   3

This sounds like the job for scan methods (compare e.g. with Haskell's scanl), e.g. std::transform_exclusive_scan:

#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main() {
  std::vector v{0, 0, 0, 0};
  int value_increment = 1;
  std::transform_inclusive_scan(
      v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "),
      std::plus<int>{},
      [&value_increment](int x) { return x   value_increment  ; });
  // 1 3 6 10
}

CodePudding user response：

You could use some metaprogramming tricks and make the compiler unroll the loop for you during the compilation process: (This should also be quite faster than an ordinary runtime for-loop. See loop unrolling for more information.)

// Do note that this Only works with C  11 or above
#include <type_traits>

template <std::size_t N, std::size_t I>
auto update(int(&arr)[N]) -> typename std::enable_if<(I == N)>::type {}

template <std::size_t N, std::size_t I = 0>
auto update(int(&arr)[N]) -> typename std::enable_if<(I < N)>::type {
    arr[I] = arr[I]   (I   1);
    update<N, I   1>(arr);
}

Then you can use it like this:

#include <iostream>

int main() {
    int arr[] {1, 2, 3, 4, 5};
    update(arr);
    for (auto const& elem : arr)
        std::cout << elem << " "; // 2 4 6 8 10
}

CodePudding user response：

You're changing every member in a range in a similar way, so std::transform does what you want. (Example not compiled or tested)

int i = 0;
std::transform(std::begin(v), std::end(v), std::begin(v),
               [&](int e) { return e   (  i); });

CodePudding user response：

This in my for loop version, using std::array. If start and end is known at runtime instead, change std::array to std::vector.

#include <iostream>
#include <array>

int main()
{
    const int start{0};
    const int end{10};

    std::array<long long, end> v{0,0,0,0,0,0,0,0,0,0};

    std::array<long long, end> updateQ {1,2,3,4,5,6,7,8,9,10};


    for(int i {start}; i < end;   i)
    {
        v[i]  = updateQ[i] * (i - start   1);
    }
    for(const int &i : v) std::cout << i << ' ';

    return 0;
}