Li Chao Tree を書いた - kaage精進録

Li Chao Tree を書いた. 一次関数 $y=a_ix+b_i$ の追加と, $x=p$ での取る値の最小値の取得が、取得したい点の集合のサイズを $N$ としてそれぞれ $O(\log N)$ になるデータ構造.

使い道

最適化DPの遷移でこういう式が出てくることがあって, これで高速化ができることがある. JOI で出ることもある.

発想

LCT は CHT の実現方法の一だというのを聞いたことがあるが, 自分は違うと思っている. CHTでは, 一次係数と値の凸性を利用して直線の追加やクエリへの応答を行うが, LCT で本質となるのは, それぞれの直線が最小値をとる部分が区間となることである.

一次関数が複数あるとき, ある関数が最小値をとる部分がひとつの区間になるのは自明だろう. この区間の管理を簡単にできるようにしたのが CHT だと思っている.

LCT では, Segment Tree と同様に, 2べき区間に直線の枠を割当る. ある点での最小値を求めるには, その点を含むすべての区間の直線だけ考えればよい構造になっている. ただし, クエリに使うそれぞれの点は先に判明していないといけない. これがまったく判明していなければ, 動的メモリ確保をしながら実装をする必要が出てくる.

実装の詳細から説明するとわかりやすいかもしれない. 直線の追加の際のことを考える. 上位の区間から順に辿っていき, もしすでにある直線と交わらなければ, 最小値を取る方を設定して更新をやめる. もし交わっていれば, その区間内の点の半分以上で最小値をとれるように直線を設定し, 交点がある方の下位区間へと進んでいく. 詳細な図を交えた解説はこれがわかりやすかった.

このアルゴリズムでなぜ正しくクエリに応答できるかどうかをもう少し考える. ある点である関数が最小値をとるとき, その点を含む $O(\log N)$ 個の区間のどこかにその関数があればよい. この条件が満たされているかについて考えたとき, ある直線追加の前後で数学的帰納法を用いれば, このアルゴリズムがいつでも正しくクエリ処理可能な木を構築できることがわかる.

また, これを応用して線分の追加もできる. 高々 $O(\log N)$ 個の区間に追加すればいいので, $O(\log^2 N)$ になる.

実装

定数倍はたぶんそこそこ. 線分追加も, 非再帰 Segment Tree の要領で追加すべき区間を明らかにして内部でも非再帰で処理すれば, 完全に非再帰で実装できるはず.

とりあえず直線追加だけのバージョンを（線分追加はあとで機能追加するかも）

class LiChaoTree{
    int n=1;
    std::vector<std::tuple<lint,lint,lint>> interval;
    std::vector<LP> node;
    std::vector<lint> cord;
    lint calc(LP l,lint x){
        return l.first*x+l.second;
    }
public:
    LiChaoTree(std::vector<lint> vec){
        vec.emplace_back(vec.back()+1);
        while(n<(int)vec.size())n*=2;
        while((int)vec.size()<n+1)vec.emplace_back(vec.back()+1);
        node.assign(2*n,{0,LINF});
        interval.emplace_back(0,0,0);
        for(int range=n;range;range>>=1){
            for(int i=0;i<n;i+=range){
                if(range==1)interval.emplace_back(vec[i],0,vec[i+range]);
                else interval.emplace_back(vec[i],vec[i+range/2],vec[i+range]);
            }
        }
        cord=std::move(vec);
    }
    void addLine(lint a,lint b){
        int cnt=1;
        while(true){
            lint l=std::get<0>(interval[cnt]),m=std::get<1>(interval[cnt]),r=std::get<2>(interval[cnt]);
            if(n<=cnt){
                if(calc(node[cnt],l)>calc({a,b},l))node[cnt]={a,b};
                break;
            }
            if(calc(node[cnt],l)<calc({a,b},l)&&calc(node[cnt],r)<calc({a,b},r))break;
            if(calc(node[cnt],l)>calc({a,b},l)&&calc(node[cnt],r)>calc({a,b},r)){
                node[cnt]={a,b};
                break;
            }
            if(calc(node[cnt],m)>calc({a,b},m)){
                LP memo=node[cnt];
                node[cnt]={a,b};
                a=memo.first;b=memo.second;
            }
            if(calc(node[cnt],l)>calc({a,b},l))cnt=cnt<<1;
            else cnt=cnt<<1|1;
        }
    }
    lint query(int idx){
        lint x=cord[idx];
        idx+=n;
        lint res=LINF;
        while(idx){
            chmin(res,calc(node[idx],x));
            idx>>=1;
        }
        return res;
    }
};