data_structure/range_add_point_get.hpp

View this file on GitHub
Last update: 2024-02-24 21:55:02+09:00
Include: #include "data_structure/range_add_point_get.hpp"

Depends on

Code

#pragma once

#include "fenwick_tree.hpp"

template <typename T>
class RangeAddPointGet {
    int n;
    FenwickTree<Add<T>> ft;

public:
    RangeAddPointGet(int n) : n(n), ft(n + 1) {}

    void add(int l, int r, const T &v) {
        assert(0 <= l && l <= r && r <= n);
        ft.add(l, v);
        ft.add(r, -v);
    }

    T get(int idx) const {
        assert(0 <= idx && idx < n);
        return ft.sum(idx + 1);
    }
};

#line 2 "data_structure/range_add_point_get.hpp"

#line 2 "data_structure/fenwick_tree.hpp"

#include <cassert>
#include <vector>
#line 2 "data_structure/operations.hpp"

#include <algorithm>
#include <limits>
#include <utility>

template <typename T>
struct Add {
    using Value = T;
    static Value id() { return T(0); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs + rhs; }
    static Value inv(const Value &x) { return -x; }
};

template <typename T>
struct Mul {
    using Value = T;
    static Value id() { return Value(1); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs * rhs; }
    static Value inv(const Value &x) { return Value(1) / x; }
};

template <typename T>
struct Min {
    static_assert(std::numeric_limits<T>::is_specialized);
    using Value = T;
    static Value id() { return std::numeric_limits<T>::max(); }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::min(lhs, rhs);
    }
};

template <typename T>
struct Max {
    static_assert(std::numeric_limits<T>::is_specialized);
    using Value = T;
    static Value id() { return std::numeric_limits<Value>::min(); }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::max(lhs, rhs);
    }
};

template <typename T>
struct Xor {
    using Value = T;
    static Value id() { return T(0); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs ^ rhs; }
    static Value inv(const Value &x) { return x; }
};

template <typename Monoid>
struct Reversible {
    using Value = std::pair<typename Monoid::Value, typename Monoid::Value>;
    static Value id() { return Value(Monoid::id(), Monoid::id()); }
    static Value op(const Value &v1, const Value &v2) {
        return Value(Monoid::op(v1.first, v2.first),
                     Monoid::op(v2.second, v1.second));
    }
};
#line 6 "data_structure/fenwick_tree.hpp"

template <typename CommutativeGroup>
class FenwickTree {
public:
    using Value = typename CommutativeGroup::Value;

private:
    std::vector<Value> data;

public:
    FenwickTree(int n) : data(n, CommutativeGroup::id()) {}

    void add(int idx, const Value &x) {
        assert(idx >= 0 && idx < (int)data.size());
        for (; idx < (int)data.size(); idx |= idx + 1) {
            data[idx] = CommutativeGroup::op(data[idx], x);
        }
    }

    Value sum(int r) const {
        assert(r >= 0 && r <= (int)data.size());
        Value ret = CommutativeGroup::id();
        for (; r > 0; r &= r - 1) {
            ret = CommutativeGroup::op(ret, data[r - 1]);
        }
        return ret;
    }

    Value sum(int l, int r) const {
        assert(l >= 0 && l <= r && r <= (int)data.size());
        return CommutativeGroup::op(sum(r), CommutativeGroup::inv(sum(l)));
    }
};

template <typename T>
using FenwickTreeAdd = FenwickTree<Add<T>>;
#line 4 "data_structure/range_add_point_get.hpp"

template <typename T>
class RangeAddPointGet {
    int n;
    FenwickTree<Add<T>> ft;

public:
    RangeAddPointGet(int n) : n(n), ft(n + 1) {}

    void add(int l, int r, const T &v) {
        assert(0 <= l && l <= r && r <= n);
        ft.add(l, v);
        ft.add(r, -v);
    }

    T get(int idx) const {
        assert(0 <= idx && idx < n);
        return ft.sum(idx + 1);
    }
};