Segment Tree (generalized with monoids) (examples/cpp/segment_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-21 05:38:13+09:00
• Include: #include "examples/cpp/segment_tree.hpp"
• Link: https://en.wikipedia.org/wiki/Segment_tree

Operations

For a monoid $M = (M, \cdot, 1)$ and a list $a = (a_0, a_1, \dots, a _ {n - 1}) \in M^N$ of elements $M$ with the length $N$, a segment tree can process following operations with $O(\log N)$:

• $\mathtt{point\unicode{95}set}(i, b)$: Update $a_i \gets b$
• $\mathtt{range\unicode{95}get}(l, r)$: Calculate the product $a_l \cdot a _ {l + 1} \cdot \dots \cdot a _ {r - 1}$

Depends on

• examples/cpp/monoids.hpp

Verified with

• examples/cpp/segment_tree_tests/segment_tree.point_set_range_composite.cpp
• examples/cpp/segment_tree_tests/segment_tree.range_minimum_query.cpp
• examples/cpp/segment_tree_tests/segment_tree.range_sum_query.cpp

Code

#pragma once
#include <cassert>
#include <vector>
#include "examples/cpp/monoids.hpp"

/**
 * @brief a Segment Tree (generalized with monoids) 
 * @tparam Monoid is a monoid; commutativity is not required
 * @see https://en.wikipedia.org/wiki/Segment_tree
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    const Monoid mon;
    int n;
    std::vector<value_type> a;

    segment_tree() = default;
    segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
        n = 1; while (n < n_) n *= 2;
        a.resize(2 * n - 1, mon.unit());
    }

    /**
     * @brief set $a_i$ as b in $O(\log n)$
     * @arg i is 0-based
     */
    void point_set(int i, value_type b) {
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
        for (i = (i + n) / 2; i > 0; i /= 2) {  // 1-based
            a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
        }
    }

    /**
     * @brief compute $a_l \cdot a _ {l + 1} \cdot ... \cdot a _ {r - 1}$ in $O(\log n)$
     * @arg l, r are 0-based
     */
    value_type range_concat(int l, int r) {
        assert (0 <= l and l <= r and r <= n);
        value_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
        }
        return mon.mult(lacc, racc);
    }
};

typedef segment_tree<plus_monoid> plus_segment_tree;
typedef segment_tree<max_monoid> max_segment_tree;
typedef segment_tree<min_monoid> min_segment_tree;

#line 2 "examples/cpp/segment_tree.hpp"
#include <cassert>
#include <vector>
#line 2 "examples/cpp/monoids.hpp"
#include <algorithm>
#include <cstdint>

struct plus_monoid {
    typedef int64_t value_type;
    value_type unit() const { return 0; }
    value_type mult(value_type a, value_type b) const { return a + b; }
};

struct max_monoid {
    typedef int64_t value_type;
    value_type unit() const { return INT64_MIN; }
    value_type mult(value_type a, value_type b) const { return std::max(a, b); }
};

struct min_monoid {
    typedef int64_t value_type;
    value_type unit() const { return INT64_MAX; }
    value_type mult(value_type a, value_type b) const { return std::min(a, b); }
};
#line 5 "examples/cpp/segment_tree.hpp"

/**
 * @brief a Segment Tree (generalized with monoids) 
 * @tparam Monoid is a monoid; commutativity is not required
 * @see https://en.wikipedia.org/wiki/Segment_tree
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    const Monoid mon;
    int n;
    std::vector<value_type> a;

    segment_tree() = default;
    segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
        n = 1; while (n < n_) n *= 2;
        a.resize(2 * n - 1, mon.unit());
    }

    /**
     * @brief set $a_i$ as b in $O(\log n)$
     * @arg i is 0-based
     */
    void point_set(int i, value_type b) {
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
        for (i = (i + n) / 2; i > 0; i /= 2) {  // 1-based
            a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
        }
    }

    /**
     * @brief compute $a_l \cdot a _ {l + 1} \cdot ... \cdot a _ {r - 1}$ in $O(\log n)$
     * @arg l, r are 0-based
     */
    value_type range_concat(int l, int r) {
        assert (0 <= l and l <= r and r <= n);
        value_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
        }
        return mon.mult(lacc, racc);
    }
};

typedef segment_tree<plus_monoid> plus_segment_tree;
typedef segment_tree<max_monoid> max_segment_tree;
typedef segment_tree<min_monoid> min_segment_tree;

Back to top page