Undoable Li Chao Tree
(data-structure/cht/undoable_li_chao_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-08 01:32:22+09:00
• Include: #include "data-structure/cht/undoable_li_chao_tree.hpp"

Required by

• Offline Deletable Convex Hull Trick (data-structure/cht/offline_deletable_convex_hull_trick.hpp)

Code

#pragma once
#include <algorithm>
#include <bit>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

/**
 * @brief Undoable Li Chao Tree
 */
template <typename T>
class UndoableLiChaoTree {
   public:
    UndoableLiChaoTree() = default;
    explicit UndoableLiChaoTree(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
        size = std::bit_ceil(xs.size());
        node.resize(2 * size, {0, INF});
        while ((int)xs.size() <= size) xs.push_back(xs.back() + 1);
    }

    void add(T a, T b) {
        history.emplace_back(-1, Line(0, 0));
        Line line(a, b);
        int k = 1, l = 0, r = size;
        while (true) {
            int m = std::midpoint(l, r);
            bool left = line(xs[l]) < node[k](xs[l]);
            bool mid = line(xs[m]) < node[k](xs[m]);
            bool right = line(xs[r]) < node[k](xs[r]);

            if (!left && !right) break;
            if (left && right) {
                history.emplace_back(k, node[k]);
                node[k] = line;
                break;
            }
            if (mid) {
                history.emplace_back(k, node[k]);
                std::swap(node[k], line);
            }
            if (r - l == 1) break;
            if (left != mid) {
                k = 2 * k;
                r = m;
            } else {
                k = 2 * k + 1;
                l = m;
            }
        }
    }

    T get(T x) const {
        int k = std::ranges::lower_bound(xs, x) - xs.begin();
        k += size;
        T res = node[k](x);
        while (k >>= 1) res = std::min(res, node[k](x));
        return res;
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [k, line] = history.back();
            history.pop_back();
            if (k == -1) break;
            node[k] = line;
        }
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a * x + b; }
    };

    static constexpr T INF = std::numeric_limits<T>::max();

    int size;
    std::vector<T> xs;
    std::vector<Line> node;
    std::vector<std::pair<int, Line>> history;
};

#line 2 "data-structure/cht/undoable_li_chao_tree.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

/**
 * @brief Undoable Li Chao Tree
 */
template <typename T>
class UndoableLiChaoTree {
   public:
    UndoableLiChaoTree() = default;
    explicit UndoableLiChaoTree(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
        size = std::bit_ceil(xs.size());
        node.resize(2 * size, {0, INF});
        while ((int)xs.size() <= size) xs.push_back(xs.back() + 1);
    }

    void add(T a, T b) {
        history.emplace_back(-1, Line(0, 0));
        Line line(a, b);
        int k = 1, l = 0, r = size;
        while (true) {
            int m = std::midpoint(l, r);
            bool left = line(xs[l]) < node[k](xs[l]);
            bool mid = line(xs[m]) < node[k](xs[m]);
            bool right = line(xs[r]) < node[k](xs[r]);

            if (!left && !right) break;
            if (left && right) {
                history.emplace_back(k, node[k]);
                node[k] = line;
                break;
            }
            if (mid) {
                history.emplace_back(k, node[k]);
                std::swap(node[k], line);
            }
            if (r - l == 1) break;
            if (left != mid) {
                k = 2 * k;
                r = m;
            } else {
                k = 2 * k + 1;
                l = m;
            }
        }
    }

    T get(T x) const {
        int k = std::ranges::lower_bound(xs, x) - xs.begin();
        k += size;
        T res = node[k](x);
        while (k >>= 1) res = std::min(res, node[k](x));
        return res;
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [k, line] = history.back();
            history.pop_back();
            if (k == -1) break;
            node[k] = line;
        }
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a * x + b; }
    };

    static constexpr T INF = std::numeric_limits<T>::max();

    int size;
    std::vector<T> xs;
    std::vector<Line> node;
    std::vector<std::pair<int, Line>> history;
};

Back to top page