I found LiChao Tree easier to understand/implement, this is a good explanation

I use this code written by niklasb. Note my comment in link, the original code has a bug.

// Keeps upper hull for maximums. 
// add lines with -m and -b and return -ans to 
// make this code working for minimums. 
// source: http://mirror.codeforces.com/blog/entry/11155?#comment-162462
int inf = 2e18;
struct Line {
    int m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != inf) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        int x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct CHT : public multiset<Line> { 
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return 1.0 * (x->b - y->b)*(z->m - y->m) >= 1.0 * (y->b - z->b)*(y->m - x->m);
    }
    void insertLine(int m, int b) {
        auto y = insert({ m, b});
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        while (y != begin() && bad(prev(y))) erase(prev(y));
        if(y != begin()) prev(y)->succ = [=] { return &*y; };
    }
    int eval(int x) {
        auto l = *lower_bound((Line) { x, inf});
        return l.m * x + l.b;
    }
};

Write a sqrt decomp version. Keep a buffer of lines, apart from the CHT structure.. When new line is given, add to buffer. and when buffer size exceeds some B, remake the whole CHT structure. During query, query on the CHT structure as well as evaluate all lines in the buffer. Set B= sqrt(n). This works almost as fast as the set implementation, and is very easy to code imo.