structure/class/point-add-rectangle-sum.hpp

• View this file on GitHub
• Last update: 2024-08-10 03:11:07+09:00
• Include: #include "structure/class/point-add-rectangle-sum.hpp"

Depends on

• Binary Indexed Tree (structure/others/binary-indexed-tree.hpp)

Verified with

• test/verify/yosupo-point-add-rectangle-sum-4.test.cpp

Code

#include "../others/binary-indexed-tree.hpp"

template <typename T>
struct PointAddRectangleSum {
  using S = T;
  using D = BinaryIndexedTree<T>;
  static constexpr S op(const S& a, const S& b) { return a + b; }
  static constexpr S e() { return 0; }
  static constexpr D init(int n) { return D{n}; }
  static constexpr void apply(D& d, int k, const S& v) { d.apply(k, v); }
  static constexpr S prod(D& d, int l, int r) { return d.prod(l, r); }
};

#line 1 "structure/others/binary-indexed-tree.hpp"
template <typename T>
struct BinaryIndexedTree {
 private:
  int n;
  vector<T> data;

 public:
  BinaryIndexedTree() = default;

  explicit BinaryIndexedTree(int n) : n(n) { data.assign(n + 1, T()); }

  explicit BinaryIndexedTree(const vector<T> &v)
      : BinaryIndexedTree((int)v.size()) {
    build(v);
  }

  void build(const vector<T> &v) {
    assert(n == (int)v.size());
    for (int i = 1; i <= n; i++) data[i] = v[i - 1];
    for (int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if (j <= n) data[j] += data[i];
    }
  }

  void apply(int k, const T &x) {
    for (++k; k <= n; k += k & -k) data[k] += x;
  }

  T prod(int r) const {
    T ret = T();
    for (; r > 0; r -= r & -r) ret += data[r];
    return ret;
  }

  T prod(int l, int r) const { return prod(r) - prod(l); }

  int lower_bound(T x) const {
    int i = 0;
    for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] < x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }

  int upper_bound(T x) const {
    int i = 0;
    for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] <= x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }
};
#line 2 "structure/class/point-add-rectangle-sum.hpp"

template <typename T>
struct PointAddRectangleSum {
  using S = T;
  using D = BinaryIndexedTree<T>;
  static constexpr S op(const S& a, const S& b) { return a + b; }
  static constexpr S e() { return 0; }
  static constexpr D init(int n) { return D{n}; }
  static constexpr void apply(D& d, int k, const S& v) { d.apply(k, v); }
  static constexpr S prod(D& d, int l, int r) { return d.prod(l, r); }
};

Back to top page