Li chao #16

Fr0benius · 2020-09-15T05:31:25Z

No description provided.

Merge upstream

src/li_chao.rs

EbTech · 2020-09-18T20:36:20Z

src/li_chao.rs

+    /// midpoint, so we propagate it to that segment. This sequence ensures that the invariant is
+    /// kept.
+    fn add_line_impl(&mut self, mut m: i64, mut b: i64, ix: usize, l: i64, r: i64) {
+        let x = (l + r) / 2;


Hm I think you could do something like:
let (ref mut m_ix, ref mut b_ix) = self.lines[ix];

Done. Would something like let (m_ix, b_ix) = &self.lines[ix] also work, or is there something wrong with that?

I think you would have a typing error there because a reference to a pair is not the same as a pair of references. They have to be converted.

Whoa never mind you're absolutely right! I was just confused because although
let (m_ix, b_ix) = &mut self.lines[ix] compiles,
let (m_ix, b_ix): (&mut i64, &mut i64) = &mut self.lines[ix] does not!

src/li_chao.rs

EbTech · 2020-09-18T20:47:08Z

src/li_chao.rs

+    /// beat the winner on some segment, either to the left or to the right of the current
+    /// midpoint, so we propagate it to that segment. This sequence ensures that the invariant is
+    /// kept.
+    fn add_line_impl(&mut self, mut m: i64, mut b: i64, ix: usize, l: i64, r: i64) {


It would involve some funky transformations, but I believe it's possible to use dynamic_arq::ArqView instead of ix, l, r if you feel so inclined :P

Actually, better yet, is it possible to just use r-l+1 nodes instead of four times that? There's no need for the subtree to again include the middle node, right? So instead, you'd start your search in the middle node, then go either left or right. Anything wrong with this idea?

I am not sure what you mean about including the middle node. Is there a way to get rid of some of the nodes? I think they are all needed.

The standard bound for segment tree nodes is 4N; if N is a power of 2 it's 2N but I think we need around 4N if N is slightly higher than a power of 2. That's one of the reasons the AlCash style is more efficient. That one has a bound of 2N regardless of N. But I don't know if it's easy to convert Li Chao trees to that style - they are inherently top-down, moreso than normal segment trees.

Converting to use the ArqView interface would be an interesting puzzle... I wonder if it can be done while keeping time/space complexity.

Space optimization added in latest update.

EbTech · 2020-09-18T20:47:52Z

src/li_chao.rs

@@ -0,0 +1,99 @@
+/// A structure for answering minimum queries on a set of linear functions. Supports two


note: our other convex hull trick now searches for the max

OK, I will flip everything to keep things consistent.

Fr0benius

Made the changes (min to max, some small tweaks)

Fr0benius · 2022-05-22T21:19:52Z

It took two years, but the eagerly awaited space optimization is finally here!

I validated the code on a contest training problem: https://gist.github.com/Fr0benius/9d0bf0bc4891c31f5d2f0bcaa7b9b533

This passes the same tests as in the sqrt decomposition implementation, but hasn't been stress tested.

EbTech · 2023-03-09T03:59:08Z

Oh no, I can't seem to diff against the previous version that I reviewed! Is there a way?

EbTech · 2023-03-09T04:01:10Z

src/li_chao.rs

@@ -0,0 +1,110 @@
+/// A structure for answering maximum queries on a set of linear functions. Supports two
+/// operations: inserting a linear function and querying for maximum at a given point. Unlike the
+/// simplest convex hull trick implementation, the queries can be done in any order, and we can do


I'm curious, what's the simple implementation? I don't think the one in order.rs has this limitation; it might be more useful to explicitly compare against that version.

By the way, it's not necessary for the nodes to be consecutive integers is it? As long as we know all the query locations (xs) in advance... (edit: oh yeah your comment about dynamic trees sort of includes this. You might say a word about static but known xs right before mentioning the dynamic extension.)

The simplest version doesn't do any sqrt decomposition or anything like that, it just adds lines in increasing-slope order. I'm not as familiar with your algorithm, but I can change the wording here.

EbTech · 2023-03-09T04:21:57Z

src/li_chao.rs

+            std::mem::swap(&mut m, m_ix);
+            std::mem::swap(&mut b, b_ix);
+        }
+        if m < self.lines[ix].0 {


Why not use the m_ix variable again here?

EbTech · 2023-03-09T04:43:28Z

src/li_chao.rs

+        // the first i+1 lines.
+        let results = [
+            [-3, -3, -3, -3, -3, -3],
+            [-0, -1, -2, -3, -3, -3],


lol what's with the negative zeros?

Haha I don't know, maybe I wanted it to line up with the previous line

Haha it almost worked, until 1s started appearing

EbTech · 2023-03-09T04:45:37Z

src/li_chao.rs

+        for (&(slope, intercept), expected) in lines.iter().zip(results.iter()) {
+            li_chao.add_line(slope, intercept);
+            let ys: Vec<i64> = xs.iter().map(|&x| li_chao.query(x)).collect();
+            assert_eq!(expected, &ys[..]);


Does this work without the [..]?

No, it can't compare an array and a vector if you don't convert to a slice first.

Oh I see, it's the same as https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_slice
Cool.

EbTech · 2023-03-09T04:50:04Z

src/li_chao.rs

+    }
+
+    /// Finds the maximum mx+b among all lines in the structure. O(log N) complexity.
+    pub fn query(&self, x: i64) -> i64 {


It would be nice to name the methods consistently with their equivalents in order.rs.

We can discuss what these names should be; back then I settled on evaluate(x) for queries and max_with(m, b) for adding lines.

Fr0benius

Made the changes

Fr0benius · 2023-03-19T02:59:36Z

src/li_chao.rs

+        for (&(slope, intercept), expected) in lines.iter().zip(results.iter()) {
+            li_chao.add_line(slope, intercept);
+            let ys: Vec<i64> = xs.iter().map(|&x| li_chao.query(x)).collect();
+            assert_eq!(expected, &ys[..]);


No, it can't compare an array and a vector if you don't convert to a slice first.

EbTech · 2023-03-19T06:21:16Z

Looks great, I'm happy to merge it as is if you're done!

Fr0benius · 2023-03-19T20:16:23Z

Looks great, I'm happy to merge it as is if you're done!

Sure, sounds good to me!

Merge pull request #1 from EbTech/master

fdee9b6

Merge upstream

EbTech requested changes Sep 18, 2020

View reviewed changes

Fr0benius commented Sep 19, 2020

View reviewed changes

EbTech force-pushed the master branch from 82d0228 to f7e1f71 Compare September 21, 2020 04:59

EbTech mentioned this pull request Mar 6, 2021

Open to Open Source? #17

Closed

EbTech force-pushed the master branch from 1f37c99 to 64f3755 Compare July 30, 2021 18:45

Merge branch 'EbTech:master' into master

22453cd

Fr0benius force-pushed the li_chao branch from 794515c to ee1f12a Compare May 22, 2022 22:28

Fr0benius added 5 commits May 22, 2022 15:29

Merge branch 'EbTech:master' into master

03068a3

Li Chao tree, simplest implementation.

2a86a88

This passes the same tests as in the sqrt decomposition implementation, but hasn't been stress tested.

Switch min to max, minor fixes

607553e

Space optimization

9ad439d

clippy

c37757c

Fr0benius force-pushed the li_chao branch from ee1f12a to c37757c Compare May 22, 2022 22:33

Fr0benius requested a review from EbTech May 22, 2022 23:25

correct l+r < 0, small fix

ab7d29d

EbTech requested changes Mar 9, 2023

View reviewed changes

Fr0benius added 2 commits March 18, 2023 20:08

review updates

9b234c6

comments

be2aad5

Fr0benius commented Mar 19, 2023

View reviewed changes

EbTech merged commit 6c5d544 into EbTech:master Mar 19, 2023

		@@ -0,0 +1,99 @@
		/// A structure for answering minimum queries on a set of linear functions. Supports two

Li chao #16

Li chao #16

Uh oh!

Conversation

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!