Can you tell me how to find LIS in O(nlogn) time using Binary Indexed Trees? What about using Interval trees?

# | User | Rating |
---|---|---|

1 | tourist | 3869 |

2 | Benq | 3618 |

3 | Miracle03 | 3452 |

4 | peehs_moorhsum | 3429 |

5 | Radewoosh | 3417 |

6 | Petr | 3408 |

7 | maroonrk | 3386 |

8 | ko_osaga | 3339 |

9 | sunset | 3338 |

10 | jiangly | 3333 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 205 |

3 | Um_nik | 195 |

4 | Errichto | 182 |

5 | awoo | 179 |

6 | sus | 177 |

7 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | -is-this-fft- | 169 |

10 | SecondThread | 167 |

Can you tell me how to find LIS in O(nlogn) time using Binary Indexed Trees? What about using Interval trees?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/30/2021 04:15:59 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

in fenwıck tree(binary indexed tree) updating a single position and asking for query on intervals is well known algorithm. while increasing fenwick positions in sum queries , for max query you can update fenwick positions , but dont forget in max query with fenwick you can just get max of intevals begins form leftmost like this [1,i] and if you will change some point with less value this solution doesnt work. hope this helps:)

But what should you update particularly for LIS and what query you "call" to get the answer?

Well, if we calculate an array

d[value] — the length of the LIS with the last element beingvalueup to the current position in an original array, then to find the valued[currValue] we must search the maximum in prefixd[minValue;currValue–1]. And this is with BIT and segment tree. :]Can you give a code example cuz i still dont understand in :(

You can look at my solution 4380966, I do exactly the same as gen had wrote.

using segment tree: 4386727

It's pretty simple. Let

a[] be the given array, andd[] be the array defined earlier. Suppose we are ata[i]. What is the LIS that ends witha[i]? The element before the last should be less thana[i]. Let that element bevalue. Now atd[value] is the length of the LIS that ends withvalue. So we should updated[a[i]] withd[value] + 1, if it is greater thand[a[i]]. So we search for the maximumd[value] wherevalueis less thana[i]. That is why we can use BIT and segment tree to calculate the maximum on a prefixd[minValue;a[i] - 1]. As you see in Alex_2oo8 and LashaBukhnikashvili implementations, the answer is the maximum ofd[] values.@gen : d[a[i]] should not be d[i] because we are at a[i] ? and you are saying that we have to search in this range d[minValue;a[i] - 1]. Wht is minValue here ? Kindly pls explain me .I know the nlogn algorithm for the same using binary search.

It should be

d[a[i]] because we want to update the length of the LIS that ends witha[i], by the definition of arrayd[].minValueis just the smallest value in arraya[]. Typically it is simply 0.Thanks :) Understood.

@Gen In this approach if max element is greater than Array size i.e N then what should I do? I just want to know what does the each node of the tree will store?

https://www.geeksforgeeks.org/maximum-sum-increasing-subsequence-using-binary-indexed-tree/

well there is also one another solution with using same data structer , if we taking array elements in ascending order then using dp array like this

`dp[i] = answer (i is some position 1 to N)`

N is the number of elements at input , at any step there will be only less then current value at left that already updated. so we call max_query(1 , i-1), with this solution if maximum value of array elements is huge it works but yours doesnt :) , here is pseudo code :so if the a is this :

what should i do if i want to find the LIS?

maximum value of dp array is lis !!! :(

I think he meant the subsequence itself, not just the length -- you should create an additional array to store the backpointers.

int[] backpointers -- backpointers[i] = the index j < i where you continued off.

After the dp table is filled, find the index i which maximizes dp[i], then follow backpointers from there. This will give the reversed LIS.

oh sorry :) i misunderstood.

Thanks guys!!!

Excuse me for asking again but if you consider my solution what should I add to keep track of LIS elements. Sorry for disturbing you.

I understand how fenwick can be used to do max[first k els of array], but I have no idea how to recover the index 'i' such that the imaginary arr[i] = fenwick_max[0..i]. So.. idk

Other than personal choice/ease of coding, I think the more well-known dp[] approach is better not only because you can recover LIS easier, and also that particular fenwick approach is limited by the size of the values of the array -- If values extend to 10^9, it probably won't work.

Jk got it to work. Can't click the damn edit button on my other post because it's too squished, so I made a new post. http://pastebin.com/cHyeiTLk I only modified where you update dp[i], made use of tree[idx][2] to store the actual index to the input array that ends the sequence.

if values extend 10^9 you can compress them , so fenwick works:)

Thanks 1 more time

This is the comment I was looking for! Now I understood how BIT is used in LIS after 5-6 hours of searching/head scratch. Thanks ikbal, 100 likes :)

ikbal Can you elaborate on when should we use max in Fenwick? Maybe with an example!

https://codeforces.com/contest/340/submission/89817578

Hope this helps :)

Thanks, man!

It can be solved with dp using binary search, Here is tutorial.

I solved it like that

Without using trees:

Keep an array S in which every element is infinity at the beginning.

Then you read the input and every number you read, you insert it in the first position in S which contains an element greater than it (you can perform this with binary search). If you proceed in this way, S (not including the INFs) keeps the following properties at every step:

- It is an increasing subsequence;

- There exists an increasing subsequence (in the input read so far) with the same lenght of the sequence stored in S, and terminating in the same way of the sequence stored in S.

- Such increasing subsequence is as long as possible.

Note that S is not the LIS itself.

Well, I just solved it using Dijkstra's Algo. Here's the code.

It is somewhere near

`N^2`

.Simple O(n ^ 2) algorithm is faster than yours.

It was a lack of understanding. Now, when I solved it — I see more ways to do it.

Still, it can't be faster (look at the updated version, where vertices already included in queue are not added). I can't say it certainly, but looks like it's

`O(N^2)`

Here's mine BIT implementation for the same.