傾きの単調性が要らない Convex Hull Trick

はじめに

傾きに単調性がなくても insert ができる Convex Hull Trick を書きたいなーと思ったものの, 平衡二分木で書くのはめんどくさそうだし定数倍遅そうとか考えて色々調べてたら, セグメントツリーを使った簡単な方法を見つけたので, 備忘録的に書いておきます.

http://codeforces.com/blog/entry/51275
ちなみにここの記事のコメント欄で見つけたものです.
中国では Li Chao Segment Tree と呼ばれているらしいです.
あと, 自分なりの勝手な解釈が入ってるので, 元のものと少し違うかもです.

Convex Hull Trickとは

Convex Hull Trickとは, 直線集合を管理するデータ構造で, 以下の2種類のクエリをオンラインで処理できます.

直線の追加クエリ　　　　：　直線 f(x) = a * x + b を追加する
最大/最小値の取得クエリ　：　ある x に対して, 最大/最小の f(x) を求める

蟻本に載ってる deque でやるタイプは, 追加クエリの傾き a が単調非減少/増加の状況でのみ使えますが, 今回のは単調性関係なく使えます.

メインアイディア

最初に取得クエリの x のとり得る値を全列挙してソートして持っておきます.
すると, 任意の直線集合において各直線が最大/最小になりうる x の値はこの列の中の連続な区間になります.
なので, 「セグメントツリーをうまく改造するといい感じにできそう」となります.

各葉は x のとりうる値に対応させます.
ちなみにサイズを二冪で丸めるのはやめた方がいいです（一般的なINFを良い感じに決めるのがオーバーフローとかでめんどくさそうなため）. なので完全二分木になるとは限りません.

各ノードに対応する区間は, その部分木の左端の葉から右端の葉までの範囲です. このため半開区間じゃなくて閉区間で管理した方がハッピーになれます.

そして, 常に以下の性質を保ちます.

（＊）アクセスしたことの無いノードを除き, 各ノードはそのノードの区間において最大値になる可能性のある一つの直線を持っている.

追加クエリ

追加する新しい直線を f とします.
根ノードから葉に向かって下りていきます.
各ノードにおいて（そのノードの直線を g とする）, その区間の左端, 真ん中, 右端の位置で f と g の値を大小比較します.
直線同士の大小関係の性質を考えると, 以下を繰り返して追加を行えば（＊）の性質を維持できます.

もし3点全部で g の方が大きいなら, f はその区間に追加する必要がないのでそこで終了です.
もし3点全部で f の方が大きいなら, g は要らなくなるのでそのノードの直線を f に書き換えて終了です.
もし真ん中で f の方が大きいなら, f と g をスワップします. こうすると, 3点の中で f が g より大きい点は右端か左端だけになります.
左端で f が g より大きい場合は, 左の子ノードに下ります.
右端で f が g より大きい場合は, 右の子ノードに下ります.

このとき, 途中でアクセスしたことの無いノードに到達したらそのノードに f を追加して終了します.

アクセスするノード数は木の高さと同じです.
なので O(logX) (X は x の取りうる値の種類数) でできます.

取得クエリ

根ノードから目的の x の葉ノードまで下りていきながら, 各ノードで ax+b を求めていってその最大/最小値が答えです.
ただし, アクセスしたことの無いノードに到達したらそこで打ち切ります.

こちらも O(logX) です.

実装例

template <typename T, const T id>
class convex_hull_trick {
    struct line {
        T a, b;
        line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
        T get(T x) { return a * x + b; }
    };
    struct node {
        line l;
        node *lch, *rch;
        node(line l_) : l(l_), lch(nullptr), rch(nullptr) {}
        ~node() {
            if (lch) delete lch;
            if (rch) delete rch;
        }
    };

private:
    const int n;
    const vector<T> pos;
    node *root;

public:
    convex_hull_trick(const vector<T>& pos_) : n(pos_.size()), pos(pos_), root(nullptr) {}
    ~convex_hull_trick() {
        if (root) delete root;
    }
    void insert(T a, T b) {
        line l(a, b);
        root = modify(root, 0, n - 1, l);
    }
    T get(T x) const {
        int t = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
        assert(t < n && pos[t] == x);
        return sub(root, 0, n - 1, t);
    }

private:
    node* modify(node *p, int lb, int ub, line& l) {
        if (!p) return new node(l);
        if (p->l.get(pos[lb]) >= l.get(pos[lb]) && p->l.get(pos[ub]) >= l.get(pos[ub])) return p;
        if (p->l.get(pos[lb]) <= l.get(pos[lb]) && p->l.get(pos[ub]) <= l.get(pos[ub])) {
            p->l = l;
            return p;
        }
        int c = (lb + ub) / 2;
        if (p->l.get(pos[c]) < l.get(pos[c])) swap(p->l, l);
        if (p->l.get(pos[lb]) <= l.get(pos[lb]))
            p->lch = modify(p->lch, lb, c, l);
        else
            p->rch = modify(p->rch, c + 1, ub, l);
        return p;
    }
    T sub(node *p, int lb, int ub, int t) const {
        if (!p) return id;
        if (ub - lb == 0) return p->l.get(pos[t]);
        int c = (lb + ub) / 2;
        if (t <= c) return max(p->l.get(pos[t]), sub(p->lch, lb, c, t));
        return max(p->l.get(pos[t]), sub(p->rch, c + 1, ub, t));
    }
};

実装例の説明

CS Academy Squared Ends で verify してあります.
https://csacademy.com/submission/1386751/

T は a, b, x の型です.
id はその型での -INF です. これは f(x) が取りうる最小の値以下にしてください.
コンストラクタの引数は x の取りうる値を sort, unique したものを渡します.
get は最大値の取得です.
最小値を求めたい場合は中身を修正するとややこしいので, 追加時に(-a, -b) を渡して取得時にさらに - を付けて求めましょう.

わざわざ動的確保せずに配列に展開してもよかったのですが, 永続化がしやすいようにこういう実装にしてます.
もっと定数倍を速くしたいなら普通のセグメントツリーみたいに実装しましょう.

kazuma8128’s blog

競プロの面白い問題を解きます