Update $b$ to $a$ such that $b_i = \sum_{j = 0}^i a_j$ holds (tools/less_equal_moebius_inplace.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-02-21 18:33:47+09:00
• Include: #include "tools/less_equal_moebius_inplace.hpp"

template <std::ranges::random_access_range R>
requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
void less_equal_moebius_inplace(R&& b);

template <tools::group G, std::ranges::random_access_range R>
requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
void less_equal_moebius_inplace(R&& b);

Assume that the following relationship holds between $a = (a_0, a_1, \ldots, a_{N - 1})$ and $b = (b_0, b_1, \ldots, b_{N - 1})$.

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

Given $b$, it updates $b$ to $a$.

Constraints

• None

Time Complexity

• $O(N)$

License

• CC0

Author

• anqooqie

Depends on

• Concept for arithmetic types including tools::int128_t and tools::uint128_t (tools/arithmetic.hpp)
• Concept for group (tools/group.hpp)
• Typical groups (tools/groups.hpp)
• Concept for integral types including tools::int128_t and tools::uint128_t (tools/integral.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• Concept for monoid (tools/monoid.hpp)

Required by

• Find $a$ from $b$ when $b_i = \sum_{j = 0}^i a_j$ holds (tools/less_equal_moebius.hpp)

Verified with

• tests/less_equal_moebius.test.cpp

Code

#ifndef TOOLS_LESS_EQUAL_MOEBIUS_INPLACE_HPP
#define TOOLS_LESS_EQUAL_MOEBIUS_INPLACE_HPP

#include <iterator>
#include <ranges>
#include <utility>
#include "tools/group.hpp"
#include "tools/groups.hpp"

namespace tools {
  template <tools::group G, std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void less_equal_moebius_inplace(R&& b) {
    const int N = std::ranges::distance(b);
    for (int i = N - 1; i - 1 >= 0; --i) {
      std::ranges::begin(b)[i] = G::op(G::inv(std::ranges::begin(b)[i - 1]), std::ranges::begin(b)[i]);
    }
  }

  template <std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void less_equal_moebius_inplace(R&& b) {
    tools::less_equal_moebius_inplace<tools::groups::plus<std::ranges::range_value_t<R>>>(std::forward<R>(b));
  }
}

#endif

#line 1 "tools/less_equal_moebius_inplace.hpp"



#include <iterator>
#include <ranges>
#include <utility>
#line 1 "tools/group.hpp"



#include <concepts>
#line 1 "tools/monoid.hpp"



#line 5 "tools/monoid.hpp"

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 6 "tools/group.hpp"

namespace tools {
  template <typename G>
  concept group = tools::monoid<G> && requires(typename G::T x) {
    { G::inv(x) } -> std::same_as<typename G::T>;
  };
}


#line 1 "tools/groups.hpp"



#include <cstddef>
#include <type_traits>
#line 1 "tools/arithmetic.hpp"



#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 6 "tools/arithmetic.hpp"

namespace tools {
  template <typename T>
  concept arithmetic = tools::integral<T> || std::floating_point<T>;
}


#line 7 "tools/groups.hpp"

namespace tools {
  namespace groups {
    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& x, const T& y) {
        return x ^ y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return x;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& x, const T& y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& x) {
        return e() / x;
      }
    };

    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& x, const T& y) {
        return x + y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return -x;
      }
    };
  }
}


#line 9 "tools/less_equal_moebius_inplace.hpp"

namespace tools {
  template <tools::group G, std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void less_equal_moebius_inplace(R&& b) {
    const int N = std::ranges::distance(b);
    for (int i = N - 1; i - 1 >= 0; --i) {
      std::ranges::begin(b)[i] = G::op(G::inv(std::ranges::begin(b)[i - 1]), std::ranges::begin(b)[i]);
    }
  }

  template <std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void less_equal_moebius_inplace(R&& b) {
    tools::less_equal_moebius_inplace<tools::groups::plus<std::ranges::range_value_t<R>>>(std::forward<R>(b));
  }
}

Back to top page