I didn't see any documentary and blog on this topic, so I guess it's Codeforce blog time .
Prerequisite:
This blog is not a tutorial to Convex Hull Trick, so I would assume that you guys already know about it before reading this. However, I'll briefly recap for the sake of completeness.
Problem Statement: Given
This is a well-known problem, and you can find tutorial for this basically everywhere. In short, we will sort all the lines in ascending order of their slope, and remove all of the redundant lines, as shown in my beautiful painting below (A line is redundant if it lies entirely "below" its two adjacent lines). This is solvable in
Figure 1: How a redundant line looks.
From this, we observe that the resulting function is convex (since slopes are sorted). Each slope is optimal for one continuous segment, start from and end with its intersection with its two adjacent lines in the hull.
Figure 2: How the convex hull should looks, alongside its intersections.
Once the convex hull is constructed, the problem is basically just binary searching over the intersections of the convex hull to find the optimal line for queried point
struct CHT{ // casual CHT
#define Node pair<ll, ll>
vector<Node> hull, suboptimal;
vector<double> inter;
double getInter(Node a, Node b){return (double) (b.second - a.second) / (a.first - b.first);}
ll f(Node s, ll x){return s.first * x + s.second;}
void add(Node x){
if (hull.empty()) {hull.push_back(x); return;}
if (hull.back().first == x.first){
suboptimal.push_back(hull.back());
hull.pop_back();
if (inter.size()) inter.pop_back();
}
while(hull.size() >= 2){
double x1 = getInter(hull.back(), x), x2 = inter.back();
if (x1 >= x2) break;
suboptimal.push_back(hull.back());
hull.pop_back(); inter.pop_back();
}
if (hull.size()) inter.push_back(getInter(hull.back(), x));
hull.push_back(x);
}
ll get_val(ll x){
if (size() == 0) return -1e18;
int idx = lower_bound(ALL(inter), x) - inter.begin();
return f(hull[idx], x);
}
int size(){return hull.size();}
};
Time complexity:
Problem Statement: Given
Since the lines in the convex hull are sorted by slope, we observe that the further a line from the queried point, the less relevant it is.
But why is that? Let's consider two adjacent lines
Figure 3: Illustration of the lines
Thus, we only need to focus on the
Figure 4: How the algorithm may work.
However, there is a flaw to this approach. For example, for
Figure 5: How the second largest line might not be on the convex hull.
There is an easy fix! We will keep track of all of the "redundant lines" from our first run of constructing the CHT data structure, and we will use these lines to make a second CHT. So for the previous example, it would look like this.
Figure 6: How the 2-layer CHT would look like.
Then we will do the same thing for the second CHT i.e. brute forcing through the
Extending to the general case was pretty simple. We can just make
// The implementation is not optimized. I left it as it is for readability.
struct CHT{ // casual CHT
#define Node pair<ll, ll>
vector<Node> hull, suboptimal;
vector<double> inter;
double getInter(Node a, Node b){return (double) (b.second - a.second) / (a.first - b.first);}
ll f(Node s, ll x){return s.first * x + s.second;}
void add(Node x){
if (hull.empty()) {hull.push_back(x); return;}
if (hull.back().first == x.first){
suboptimal.push_back(hull.back());
hull.pop_back();
if (inter.size()) inter.pop_back();
}
while(hull.size() >= 2){
double x1 = getInter(hull.back(), x), x2 = inter.back();
if (x1 >= x2) break;
suboptimal.push_back(hull.back());
hull.pop_back(); inter.pop_back();
}
if (hull.size()) inter.push_back(getInter(hull.back(), x));
hull.push_back(x);
}
void get_val(ll x, int r, vector<ll> &ans){
int idx = lower_bound(ALL(inter), x) - inter.begin();
for(int i = idx - r; i <= idx + r; ++i) if (i >= 0 && i < size()){
ans.push_back(f(hull[i], x));
}
}
int size(){return hull.size();}
};
struct CHT_extended{ // mlg super pro vip CHT
#define Node pair<ll, ll>
int k;
vector<CHT> hull_max;
CHT_extended(int k): k(k){
for(int i = 0; i < k; ++i) hull_max.push_back(CHT());
}
void add(vector<Node> a){
for(int i = 0; i < k; ++i){ // use the suboptimal lines from the previous CHT run
sort(ALL(a));
for(Node j: a) hull_max[i].add(j);
a = hull_max[i].suboptimal; hull_max[i].suboptimal.clear();
}
}
vector<ll> get(ll x){
vector<ll> ans; ans.reserve(k * k);
for(int i = 0; i < k; ++i){ // get O(k^2) lines
hull_max[i].get_val(x, k - 1, ans);
}
if (ans.size() > k)
nth_element(ans.begin(), ans.begin() + k, ans.end(), greater<ll>());
while(ans.size() > k) ans.pop_back();
return ans; // spit back k best lines in arbitrary order. You can call sort if you want.
}
};
Time complexity:
The complexity in both the preprocessing and querying could be further optimized, but I'll leave it as an exercise for readers.
Are there any problem that feature this algorithm? Well uhh… I don't know, this is like mythical stuff that you will probably never encounter all your life. But now you have :))