segment_tree/test/segment_tree_recursion.test.cpp

View this file on GitHub
Last update: 2026-04-12 20:46:15+09: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 <iostream>

#include "../../algebra/monoid/monoid_plus.hpp"
#include "../../segment_tree/segment_tree_recursion.hpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<long long> a(N);
    for (int i = 0; i < N; i++) std::cin >> a[i];
    SegmentTreeRecursion<MonoidPlus<long long>> seg_add(a);
    SegmentTreeRecursion<MonoidPlus<long long>> seg_set(a);
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int p, x;
            std::cin >> p >> x;
            seg_add.add(p, x);
            seg_set.set(p, seg_set.get(p) + x);
        } else {
            int l, r;
            std::cin >> l >> r;
            assert(seg_add.prod(l, r) == seg_set.prod(l, r));
            std::cout << seg_add.prod(l, r) << '\n';
        }
    }
    return 0;
}

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

#include <iostream>

#line 2 "algebra/monoid/monoid_plus.hpp"

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};
#line 2 "segment_tree/segment_tree_recursion.hpp"

#include <cassert>
#include <vector>

// Segment Tree (再帰 + ポインタ木)
// 2N は N = 500000 のとき 1000000 くらい
template <class MS, int MAX_NODES = 2'000'000> struct SegmentTreeRecursion {
  public:
    using S = typename MS::value_type;

    struct Node {
        S d;
        Node *l, *r;
        Node() = default;
        Node(S v, Node* l = nullptr, Node* r = nullptr) : d(v), l(l), r(r) {}
    };

    SegmentTreeRecursion() = default;

    explicit SegmentTreeRecursion(int n)
        : SegmentTreeRecursion(std::vector<S>(n, MS::identity())) {}

    explicit SegmentTreeRecursion(const std::vector<S>& v)
        : n((int)(v.size())) {
        root = build(v, 0, n);
    }

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        set(p, x, 0, n, root);
    }

    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        add(p, x, 0, n, root);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S get(int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, 0, n, root);
    }

    S all_prod() const { return root->d; }

    std::vector<S> make_vector() const {
        std::vector<S> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i);
        return vec;
    }

  private:
    int n;
    Node* root;
    static inline Node pool[MAX_NODES];
    static inline int pool_idx = 0;

    Node* new_node(S v, Node* l = nullptr, Node* r = nullptr) {
        return &(pool[pool_idx++] = Node(v, l, r));
    }

    Node* merge(Node* l, Node* r, Node* np = nullptr) {
        if (np == nullptr) {
            np = new_node(MS::operation(l->d, r->d), l, r);
        } else {
            np->d = MS::operation(l->d, r->d);
        }
        return np;
    }

    Node* build(const std::vector<S>& v, int l, int r) {
        if (l + 1 == r) {
            return new_node(v[l]);
        }
        int m = (l + r) / 2;
        return merge(build(v, l, m), build(v, m, r));
    }

    Node* set(int p, const S& x, int l, int r, Node* np) {
        if (l + 1 == r) {
            np->d = x;
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(set(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, set(p, x, m, r, np->r), np);
        }
    }

    Node* add(int p, const S& x, int l, int r, Node* np) {
        if (l + 1 == r) {
            np->d = MS::operation(np->d, x);
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(add(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, add(p, x, m, r, np->r), np);
        }
    }

    S prod(int ql, int qr, int l, int r, Node* np) const {
        // [ql, qr) と [l, r) が交差しない
        if (qr <= l or r <= ql) return MS::identity();
        // [ql, qr) が [l, r) を完全に含んでいる
        if (ql <= l and r <= qr) return np->d;
        int m = (l + r) / 2;
        return MS::operation(prod(ql, qr, l, m, np->l),
                             prod(ql, qr, m, r, np->r));
    }
};
#line 7 "segment_tree/test/segment_tree_recursion.test.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<long long> a(N);
    for (int i = 0; i < N; i++) std::cin >> a[i];
    SegmentTreeRecursion<MonoidPlus<long long>> seg_add(a);
    SegmentTreeRecursion<MonoidPlus<long long>> seg_set(a);
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int p, x;
            std::cin >> p >> x;
            seg_add.add(p, x);
            seg_set.set(p, seg_set.get(p) + x);
        } else {
            int l, r;
            std::cin >> l >> r;
            assert(seg_add.prod(l, r) == seg_set.prod(l, r));
            std::cout << seg_add.prod(l, r) << '\n';
        }
    }
    return 0;
}