test/static_range_sum.test.cpp

View this file on GitHub
Last update: 2025-11-07 09:14:02+08:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include "../weilycoder/ds/group.hpp"
#include "../weilycoder/ds/static_range_sum.hpp"
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
using namespace weilycoder;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  size_t n, q;
  cin >> n >> q;

  vector<uint64_t> arr(n);
  for (size_t i = 0; i < n; ++i)
    cin >> arr[i];

  StaticRangeSum<AddGroup<uint64_t>> sum(arr);
  while (q--) {
    size_t l, r;
    cin >> l >> r;
    cout << sum.query(l, r) << '\n';
  }
  return 0;
}

#line 1 "test/static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#line 1 "weilycoder/ds/group.hpp"



/**
 * @file group.hpp
 * @brief Group Definitions
 */

#include <limits>

namespace weilycoder {
/**
 * @brief Additive Group
 * @tparam T Type of the elements
 */
template <typename T> struct AddGroup {
  using value_type = T;
  static constexpr T operation(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return T{}; }
  static constexpr T inverse(const T &a) { return -a; }
};

/**
 * @brief Additive Monoid
 * @tparam T Type of the elements
 */
template <typename T> struct AddMonoid {
  using value_type = T;
  static constexpr T operation(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return T{}; }
};

/**
 * @brief Minimum Monoid for numbers
 * @tparam T Type of the elements, must support std::numeric_limits
 */
template <typename T> struct NumberMinMonoid {
  using value_type = T;
  static constexpr T operation(const T &a, const T &b) { return a < b ? a : b; }
  static constexpr T identity() { return std::numeric_limits<T>::max(); }
};

/**
 * @brief Maximum Monoid for numbers
 * @tparam T Type of the elements, must support std::numeric_limits
 */
template <typename T> struct NumberMaxMonoid {
  using value_type = T;
  static constexpr T operation(const T &a, const T &b) { return a > b ? a : b; }
  static constexpr T identity() { return std::numeric_limits<T>::min(); }
};
} // namespace weilycoder


#line 1 "weilycoder/ds/static_range_sum.hpp"



/**
 * @file static_range_sum.hpp
 * @brief Static Range Sum using Prefix Sums
 */

#include <cstddef>
#include <stdexcept>
#include <vector>

namespace weilycoder {
/**
 * @brief Static Range Sum using Prefix Sums
 * @tparam Group A group defining the operation and identity element,
 *                must be associative and invertible (i.e. Group).
 */
template <typename Group> struct StaticRangeSum {
  using value_type = typename Group::value_type;
  using T = value_type;

private:
  std::vector<T> prefix_sum;

public:
  /**
   * @brief Constructs a StaticRangeSum for n elements initialized to the
   *        identity element
   * @param n Number of elements
   */
  explicit StaticRangeSum(const std::vector<T> &data)
      : prefix_sum(data.size() + 1, Group::identity()) {
    for (size_t i = 1; i <= data.size(); ++i)
      prefix_sum[i] = Group::operation(prefix_sum[i - 1], data[i - 1]);
  }

  /**
   * @brief Constructs a StaticRangeSum from an initial range
   * @tparam InputIt Input iterator type
   * @param first Beginning of the range
   * @param last End of the range
   */
  template <typename InputIt>
  StaticRangeSum(InputIt first, InputIt last)
      : prefix_sum(std::distance(first, last) + 1, Group::identity()) {
    size_t i = 1;
    for (auto it = first; it != last; ++it, ++i)
      prefix_sum[i] = Group::operation(prefix_sum[i - 1], *it);
  }

  /**
   * @brief Returns the number of elements
   * @return Number of elements
   */
  size_t size() const { return prefix_sum.size() - 1; }

  /**
   * @brief Queries the sum in the range [l, r)
   * @param l Left index (inclusive)
   * @param r Right index (exclusive)
   * @return Sum in the range [l, r)
   * @throws std::out_of_range if the range is invalid
   */
  T query(size_t l, size_t r) const {
    if (l > r || r > size())
      throw std::out_of_range("Invalid range for StaticRangeSum query");
    return Group::operation(Group::inverse(prefix_sum[l]), prefix_sum[r]);
  }
};
} // namespace weilycoder


#line 5 "test/static_range_sum.test.cpp"
#include <cstdint>
#include <iostream>
#line 8 "test/static_range_sum.test.cpp"
using namespace std;
using namespace weilycoder;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  size_t n, q;
  cin >> n >> q;

  vector<uint64_t> arr(n);
  for (size_t i = 0; i < n; ++i)
    cin >> arr[i];

  StaticRangeSum<AddGroup<uint64_t>> sum(arr);
  while (q--) {
    size_t l, r;
    cin >> l >> r;
    cout << sum.query(l, r) << '\n';
  }
  return 0;
}