Li Chao tree for Line Queries

📌 Table of Contents

1. Introduction

Li Chao tree is another technique for solving line queries problem. It is primarily used when we need to add a new line and find the maximum or minimum value at a specific point. This technique leverages the segment tree structure to quickly find the required values.

Li Chao tree differs from CHT in that it is similar to dynamic CHT, adding edges based on any angle coefficient without affecting the result

However, the Li Chao tree cannot work if the input size is too large due to the use of a segment tree (this can be addressed by compressing the numbers).

Since it is a segment tree, the add and get operations have a complexity of log(n).

Explaination:

2. Initialization

Create a segment tree using the struct line


// Li Chao tree structure
struct line
{
  ll a, b;
  ll operator()(long long x)
  {
    return a*x+b;
  }
};
line st[40*maxn];
        

3. Add function


void add(int id, int l, int r, line segment)
{
  if(l+1==r)
  {
    if(segment(l)>st[id](l))
    swap(segment,st[id]);
  }
  else
  {
    int mid = (l+r)/2;
    if(st[id].a>segment.a)  swap(segment,st[id]);
    if(segment(mid)>st[id](mid))
    {
      swap(segment,st[id]);
      add(id*2,l,mid,segment);
    }
    else
      add(id*2+1,mid,r,segment);
  }
}
        
Convex vs Concave
After swapping the two lines, we have → Red: Old Blue: New
Convex vs Concave

➤ With this approach, we can be sure that during the result retrieval process, we will find the line segment that provides the best value (Read more about the get function for further understanding)

4. Get function

Travel from the root of the tree to the leaf node to find the best possible maximum value


ll get(int id, int l, int r, ll val)
{
  if(l+1==r)
    return st[id](val);
  else
  {
    int mid = (l+r)/2;
    if(val<=mid)
      return max(st[id](val),get(id*2,l,mid,val));
    else
      return max(st[id](val),get(id*2+1,mid,r,val));
  }
}
        

5. Template


#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
const ll inf = 1e18+1;
int n,w[maxn];
ll h[maxn],sum[maxn],dp;

struct line
{
  ll a, b;
  ll operator()(long long x)
  {
    return a*x+b;
  }
};
line st[40*maxn];

void add(int id, int l, int r, line segment)
{
  if(l+1==r)
  {
    if(segment(l)<st[id](l))
      swap(segment,st[id]);
  }
  else
  {
    int mid = (l+r)/2;
    if(st[id].a>segment.a)  swap(segment,st[id]);
    if(segment(mid)<st[id](mid))
    {
      swap(segment,st[id]);
      add(id*2+1,mid,r,segment);
    }
    else
      add(id*2,l,mid,segment);
  }
}

ll get(int id, int l, int r, ll val)
{
  if(l+1==r)
    return st[id](val);
  else
  {
    int mid = (l+r)/2;
    if(val<=mid)
      return min(st[id](val),get(id*2,l,mid,val));
    else
      return min(st[id](val),get(id*2+1,mid,r,val));
  }
}

void input()
{
  for(int i=0;i<40*maxn;++i)
  {
    st[i].a=0;
    st[i].b = inf;
  }
  cin>>n;
  for(int i=1;i<=n;++i)   cin>>h[i];
  for(int i=1;i<=n;++i)   cin>>w[i];
  for(int i=1;i<=n;++i)   sum[i] = sum[i-1]+w[i];
  line tmp;
  tmp.a = -2*h[1];
  tmp.b = h[1]*h[1] - sum[1];
  add(1,0,1e6,tmp);
  for(int i=2;i<=n;++i)
  {
    dp = h[i]*h[i] + sum[i-1] + get(1,0,1e6,h[i]);
    tmp.a = -2*h[i];
    tmp.b = h[i]*h[i] - sum[i] + dp;
    add(1,0,1e6,tmp);
  }
  cout<<dp;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  return 0;
}
        

6. Problem set