Find $a$ from $b$ when $b_i = \sum_{j = i}^{N - 1} a_j$ holds (tools/greater_equal_moebius.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-11-02 18:34:38+09:00
• Include: #include "tools/greater_equal_moebius.hpp"

(1)
template <typename InputIterator, typename OutputIterator>
void greater_equal_moebius(InputIterator begin, InputIterator end, OutputIterator result);

(2)
template <typename RandomAccessIterator>
void greater_equal_moebius(RandomAccessIterator begin, RandomAccessIterator end);

• (1)
  • Given a sequence $(b_0, b_1, \ldots, b_{N - 1})$ from begin and end, it stores the sequence $(a_0, a_1, \ldots, a_{N - 1})$ that satisfies the following relational equation to result.
• (2)
  • Given a sequence $(b_0, b_1, \ldots, b_{N - 1})$ from begin and end, it stores the sequence $(a_0, a_1, \ldots, a_{N - 1})$ that satisfies the following relational equation to begin.

The following relationship holds between $a$ and $b$.

\[\begin{align*} b_i &= \sum_{i \leq j < N} a_j \end{align*}\]

Constraints

• None
  • Note that result in (1) can be the same as begin, but it would be better to use (2) in that case.

Time Complexity

• $O(N)$

License

• CC0

Author

• anqooqie

Verified with

• tests/greater_equal_moebius.test.cpp

Code

#ifndef TOOLS_GREATER_EQUAL_MOEBIUS_HPP
#define TOOLS_GREATER_EQUAL_MOEBIUS_HPP

#include <iterator>
#include <vector>
#include <algorithm>

namespace tools {
  template <typename RandomAccessIterator>
  void greater_equal_moebius(const RandomAccessIterator begin, const RandomAccessIterator end) {
    const int N = end - begin;
    for (int i = 0; i + 1 < N; ++i) {
      begin[i] -= begin[i + 1];
    }
  }

  template <typename InputIterator, typename OutputIterator>
  void greater_equal_moebius(const InputIterator begin, const InputIterator end, const OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    ::std::vector<T> b(begin, end);
    ::tools::greater_equal_moebius(b.begin(), b.end());
    ::std::move(b.begin(), b.end(), result);
  }
}

#endif

#line 1 "tools/greater_equal_moebius.hpp"



#include <iterator>
#include <vector>
#include <algorithm>

namespace tools {
  template <typename RandomAccessIterator>
  void greater_equal_moebius(const RandomAccessIterator begin, const RandomAccessIterator end) {
    const int N = end - begin;
    for (int i = 0; i + 1 < N; ++i) {
      begin[i] -= begin[i + 1];
    }
  }

  template <typename InputIterator, typename OutputIterator>
  void greater_equal_moebius(const InputIterator begin, const InputIterator end, const OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    ::std::vector<T> b(begin, end);
    ::tools::greater_equal_moebius(b.begin(), b.end());
    ::std::move(b.begin(), b.end(), result);
  }
}

Back to top page