segment_tree/test/fenwick_tree_plus.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/fenwick_tree.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];
    FenwickTree<MonoidPlus<long long>> seg_add(a);
    FenwickTree<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/fenwick_tree_plus.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/fenwick_tree.hpp"

#include <cassert>
#include <vector>

// Fenwick Tree
template <class MS> struct FenwickTree {
  public:
    using S = typename MS::value_type;

    FenwickTree() = default;

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

    explicit FenwickTree(const std::vector<S>& v) : n((int)(v.size())) {
        d = std::vector<S>(n + 1, MS::identity());
        for (int i = 1; i <= n; i++) {
            d[i] = MS::operation(d[i], v[i - 1]);
            int j = i + (i & -i);
            if (j <= n) {
                d[j] = MS::operation(d[j], d[i]);
            }
        }
    }

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        add(p, MS::operation(MS::inverse(get(p)), x));
    }
    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        p++;  // 1-indexed
        while (p <= n) {
            d[p] = MS::operation(d[p], x);
            p += p & -p;
        }
    }

    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 MS::operation(prod(r), MS::inverse(prod(l)));
    }

    S prod(int p) const {
        assert(0 <= p and p <= n);
        S s = MS::identity();
        while (p > 0) {
            s = MS::operation(s, d[p]);
            p -= p & -p;
        }
        return s;
    }

    S all_prod() const { return prod(n); }

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

  private:
    int n;
    std::vector<S> d;
};
#line 7 "segment_tree/test/fenwick_tree_plus.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];
    FenwickTree<MonoidPlus<long long>> seg_add(a);
    FenwickTree<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;
}