struct Line {
	ll a, b;
	ll eval(ll x) const { return a*x + b; }
};
class LiChao {
	private:
		const static ll INF = 4e18;
		vector<Line> tree; // Tree of lines
		vector<ll> xs; // x-coordinate of point i
		int k = 1; // Log-depth of the tree

		int mapInd(int j) const {
			int z = __builtin_ctz(j);
			return ((1<<(k-z)) | (j>>z)) >> 1;
		}
		bool comp(const Line& a, int i, int j) const {
			return a.eval(xs[j]) < tree[i].eval(xs[j]);
		}
	public:
		LiChao(const vector<ll>& points) {
			while(points.size() >> k) ++k;
			tree.resize(1 << k, {0, INF});
			xs.resize(1 << k, points.back());
			for (int i = 0; i < points.size(); ++i) xs[mapInd(i+1)] = points[i];
		}
		void addLine(Line line) {
			for (int i = 1; i < tree.size();) {
				if (comp(line, i, i)) swap(line, tree[i]);
				if (line.a > tree[i].a) i = 2*i;
				else i = 2*i+1;
			}
		}
		ll minVal(int j) const {
			j = mapInd(j+1);
			ll res = INF;
			for (int i = j; i > 0; i /= 2) res = min(res, tree[i].eval(xs[j]));
			return res;
		}
};

Tässä mapInd-funktio kuvaa indeksit sijainteihin puussa. Jos puun koko on 7, ja arvot x ovat 1, 2, \dots, 7, puun indeksointi on seuraava

ja arvot x sen solmuissa ovat seuraavat

Toinen, segmenttipuutyylinen toteutus:

const int N = 1<<20;
const ll INF = 4e18;
struct Line {
	// Nämä voi usein tallentaa intteinä, mutta tällöin
	// "ääretön" suora pitää toteuttaa varovasti.
	ll k, c=INF;
	ll operator()(ll x) {
		return k*x + c;
	}
} lct[2*N];
Line lc_get(int p, int cn=1, int x=0, int y=N-1) {
	if (x == y) return lct[cn];
	int m = (x+y)/2;
	Line got;
	if (p <= m) got = lc_get(p, 2*cn, x, m);
	else got = lc_get(p, 2*cn+1, m+1, y);
	if (lct[cn](p) < got(p)) return lct[cn];
	else return got;
}
void lc_add(Line nw, int cn=1, int x=0, int y=N-1) {
	Line &old = lct[cn];
	int m = (x+y)/2;
	bool better_x = nw(x) < old(x);
	bool better_m = nw(m) < old(m);
	if (better_m) swap(old, nw);
	if (x != y) {
		if (better_x != better_m) {
			lc_add(nw, 2*cn, x, m);
		} else {
			lc_add(nw, 2*cn+1, m+1, y);
		}
	}
}