data_structure/segment_tree.hpp

• View this file on GitHub
• Last update: 2023-12-26 16:56:23+09:00
• Include: #include "data_structure/segment_tree.hpp"

Depends on

• data_structure/operations.hpp

Verified with

• data_structure/test/point_set_range_composite.test.cpp

Code

#pragma once

#include <cassert>
#include <utility>
#include <vector>
#include "operations.hpp"

template <typename Monoid>
class SegmentTree {
public:
    using Value = typename Monoid::Value;

private:
    int old_length;
    int length;
    std::vector<Value> node;

    static int ceil2(int n) {
        int l = 1;
        while (l < n) {
            l <<= 1;
        }
        return l;
    }

public:
    SegmentTree(int n)
        : old_length(n),
          length(ceil2(old_length)),
          node(length << 1, Monoid::id()) {
        assert(n >= 0);
    }

    SegmentTree(const std::vector<Value> &v)
        : old_length((int)v.size()),
          length(ceil2(old_length)),
          node(length << 1, Monoid::id()) {
        for (int i = 0; i < old_length; ++i) {
            node[i + length] = v[i];
        }
        for (int i = length - 1; i > 0; --i) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }

    template <typename F>
    SegmentTree(int n, const F &f)
        : old_length(n), length(ceil2(n)), node(length << 1, Monoid::id()) {
        assert(n >= 0);
        for (int i = 0; i < old_length; ++i) {
            node[i + length] = f(i);
        }
        for (int i = length - 1; i > 0; --i) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }

    const Value &operator[](int idx) const {
        assert(idx >= 0 && idx < old_length);
        return node[idx + length];
    }

    void update(int idx, Value val) {
        assert(idx >= 0 && idx < old_length);
        idx += length;
        node[idx] = std::move(val);
        while (idx != 1) {
            idx >>= 1;
            node[idx] = Monoid::op(node[idx << 1], node[idx << 1 | 1]);
        }
    }

    Value prod(int l, int r) const {
        assert(l >= 0 && l <= r && r <= old_length);
        Value prodl = Monoid::id();
        Value prodr = Monoid::id();
        l += length;
        r += length;
        while (l != r) {
            if (l & 1) {
                prodl = Monoid::op(prodl, node[l++]);
            }
            if (r & 1) {
                prodr = Monoid::op(node[--r], prodr);
            }
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(prodl, prodr);
    }

    Value all_prod() const { return node[1]; }
};

#line 2 "data_structure/segment_tree.hpp"

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

#include <algorithm>
#include <limits>
#line 6 "data_structure/operations.hpp"

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 7 "data_structure/segment_tree.hpp"

template <typename Monoid>
class SegmentTree {
public:
    using Value = typename Monoid::Value;

private:
    int old_length;
    int length;
    std::vector<Value> node;

    static int ceil2(int n) {
        int l = 1;
        while (l < n) {
            l <<= 1;
        }
        return l;
    }

public:
    SegmentTree(int n)
        : old_length(n),
          length(ceil2(old_length)),
          node(length << 1, Monoid::id()) {
        assert(n >= 0);
    }

    SegmentTree(const std::vector<Value> &v)
        : old_length((int)v.size()),
          length(ceil2(old_length)),
          node(length << 1, Monoid::id()) {
        for (int i = 0; i < old_length; ++i) {
            node[i + length] = v[i];
        }
        for (int i = length - 1; i > 0; --i) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }

    template <typename F>
    SegmentTree(int n, const F &f)
        : old_length(n), length(ceil2(n)), node(length << 1, Monoid::id()) {
        assert(n >= 0);
        for (int i = 0; i < old_length; ++i) {
            node[i + length] = f(i);
        }
        for (int i = length - 1; i > 0; --i) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }

    const Value &operator[](int idx) const {
        assert(idx >= 0 && idx < old_length);
        return node[idx + length];
    }

    void update(int idx, Value val) {
        assert(idx >= 0 && idx < old_length);
        idx += length;
        node[idx] = std::move(val);
        while (idx != 1) {
            idx >>= 1;
            node[idx] = Monoid::op(node[idx << 1], node[idx << 1 | 1]);
        }
    }

    Value prod(int l, int r) const {
        assert(l >= 0 && l <= r && r <= old_length);
        Value prodl = Monoid::id();
        Value prodr = Monoid::id();
        l += length;
        r += length;
        while (l != r) {
            if (l & 1) {
                prodl = Monoid::op(prodl, node[l++]);
            }
            if (r & 1) {
                prodr = Monoid::op(node[--r], prodr);
            }
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(prodl, prodr);
    }

    Value all_prod() const { return node[1]; }
};

Back to top page