test/point_add_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/point_add_range_sum

Depends on

Code

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

#include "../weilycoder/ds/group.hpp"
#include "../weilycoder/ds/point_add_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> initial(n, 0);
  for (size_t i = 0; i < n; ++i)
    cin >> initial[i];

  PointAddRangeSum<AddGroup<uint64_t>> pasr(initial);
  while (q--) {
    int type;
    cin >> type;
    if (type == 0) {
      size_t i, x;
      cin >> i >> x;
      pasr.point_add(i, x);
    } else {
      size_t l, r;
      cin >> l >> r;
      cout << pasr.range_sum(l, r) << '\n';
    }
  }
  return 0;
}

#line 1 "test/point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_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/point_add_range_sum.hpp"



/**
 * @file point_add_range_sum.hpp
 * @brief Point Add Range Sum using Fenwick Tree
 */

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

namespace weilycoder {
/**
 * @brief Point Add Range Sum using Fenwick Tree (Binary Indexed Tree)
 * @tparam Group A group defining the operation and identity element,
 *                must be associative and commutative (i.e. Abelian group).
 */
template <typename Group> struct PointAddRangeSum {
  using value_type = typename Group::value_type;
  using T = value_type;

private:
  std::vector<T> data;

public:
  /**
   * @brief Constructs a PointAddRangeSum for n elements initialized to the
   *        identity element
   * @param n Number of elements
   */
  explicit PointAddRangeSum(size_t n) : data(n + 1, Group::identity()) {}

  /**
   * @brief Constructs a PointAddRangeSum from an initial array
   * @param initial Initial array of elements
   */
  explicit PointAddRangeSum(const std::vector<T> &initial)
      : data(initial.size() + 1, Group::identity()) {
    for (size_t i = 1; i <= initial.size(); ++i) {
      data[i] = Group::operation(data[i], initial[i - 1]);
      size_t j = i + (i & -i);
      if (j < data.size())
        data[j] = Group::operation(data[j], data[i]);
    }
  }

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

  size_t size() const { return data.size() - 1; }

  /**
   * @brief Adds value x to element at index i
   * @param i Index to update
   * @param x Value to add
   */
  void point_add(size_t i, const T &x) {
    for (++i; i < data.size(); i += i & -i)
      data[i] = Group::operation(data[i], x);
  }

  /**
   * @brief Computes the prefix sum [0, i)
   * @param i Index (exclusive)
   * @return The sum of elements in the range [0, i)
   */
  T prefix_sum(size_t i) const {
    if (i > size())
      throw std::out_of_range("Index out of range in prefix_sum");
    T result = Group::identity();
    for (; i > 0; i -= i & -i)
      result = Group::operation(result, data[i]);
    return result;
  }

  /**
   * @brief Computes the range sum [l, r)
   * @param l Left index (inclusive)
   * @param r Right index (exclusive)
   * @return The sum of elements in the range [l, r)
   */
  T range_sum(size_t l, size_t r) const {
    if (l > r || r > size())
      throw std::out_of_range("Invalid range for range_sum");
    return Group::operation(prefix_sum(r), Group::inverse(prefix_sum(l)));
  }
};
} // namespace weilycoder


#line 5 "test/point_add_range_sum.test.cpp"
#include <cstdint>
#include <iostream>
#line 8 "test/point_add_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> initial(n, 0);
  for (size_t i = 0; i < n; ++i)
    cin >> initial[i];

  PointAddRangeSum<AddGroup<uint64_t>> pasr(initial);
  while (q--) {
    int type;
    cin >> type;
    if (type == 0) {
      size_t i, x;
      cin >> i >> x;
      pasr.point_add(i, x);
    } else {
      size_t l, r;
      cin >> l >> r;
      cout << pasr.range_sum(l, r) << '\n';
    }
  }
  return 0;
}