### HekpoMaH's blog

By HekpoMaH, 8 years ago,

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

#### I want to officialy say a big "THANK YOU" for everyone who has helped me. +1 for everybody :)

• +27

 » 8 years ago, # |   +7 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:)
•  » » 8 years ago, # ^ |   +6 But what should you update particularly for LIS and what query you "call" to get the answer?
•  » » » 8 years ago, # ^ |   +4 Well, if we calculate an array d[value] — the length of the LIS with the last element being value up to the current position in an original array, then to find the value d[currValue] we must search the maximum in prefix d[minValue;currValue–1]. And this is with BIT and segment tree. :]
•  » » » » 8 years ago, # ^ |   +6 Can you give a code example cuz i still dont understand in :(
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +4 You can look at my solution 4380966, I do exactly the same as gen had wrote.
•  » » » » » 8 years ago, # ^ |   0 using segment tree: 4386727
•  » » » » » 8 years ago, # ^ |   +8 It's pretty simple. Let a[] be the given array, and d[] be the array defined earlier. Suppose we are at a[i]. What is the LIS that ends with a[i]? The element before the last should be less than a[i]. Let that element be value. Now at d[value] is the length of the LIS that ends with value. So we should update d[a[i]] with d[value] + 1, if it is greater than d[a[i]]. So we search for the maximum d[value] where value is less than a[i]. That is why we can use BIT and segment tree to calculate the maximum on a prefix d[minValue;a[i] - 1]. As you see in Alex_2oo8 and LashaBukhnikashvili implementations, the answer is the maximum of d[] values.
•  » » » » » » 8 years ago, # ^ | ← Rev. 3 →   0 @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.
•  » » » » » » » 8 years ago, # ^ |   0 It should be d[a[i]] because we want to update the length of the LIS that ends with a[i], by the definition of array d[].minValue is just the smallest value in array a[]. Typically it is simply 0.
•  » » » » » » » » 8 years ago, # ^ |   0 Thanks :) Understood.
•  » » » » » » 6 years ago, # ^ |   0 @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?
•  » » » » » 2 years ago, # ^ |   0
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +4 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 : let a , the array of input. let n , the lenght if a. let pos[x] , position of x at input. let dp[i] , the solution array of lis when last value of lis is a[i] let get(i) maximum value of segment [1 , i] of dp let update(i,x) dp[i] := x . sort(a) for i = 1 to n { position = pos[a[i]] answer = get(position - 1) update(position , answer + 1) } so if the a is this : 1 , 4 , 1000 , 2 , 9 after then sort 1 , 2 , 4 , 9 , 1000 dp array looks like that at each step: 1 , 0 , 0 , 0 , 0 1 , 0 , 0 , 2 , 0 1 , 2 , 0 , 2 , 0 1 , 2 , 0 , 2 , 3 1 , 2 , 3 , 2 , 3 as you see that while geting answer from left there are only less value so maximum + 1 is solution. 
•  » » » » » 8 years ago, # ^ |   +3 what should i do if i want to find the LIS?
•  » » » » » » 8 years ago, # ^ |   +3 maximum value of dp array is lis !!! :(
•  » » » » » » » 8 years ago, # ^ |   +4 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.
•  » » » » » » » » 8 years ago, # ^ |   +1 oh sorry :) i misunderstood.
•  » » » » » » » » » 8 years ago, # ^ |   0 Thanks guys!!!
•  » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » » 8 years ago, # ^ | ← Rev. 3 →   +4 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.. idkOther 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.
•  » » » » » » » » » 8 years ago, # ^ |   +1 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.
•  » » » » » » » » » 8 years ago, # ^ |   +9 if values extend 10^9 you can compress them , so fenwick works:)
•  » » » » » » » » » 8 years ago, # ^ |   0 Thanks 1 more time
•  » » » » » 16 months ago, # ^ |   0 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 :)
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 ikbal Can you elaborate on when should we use max in Fenwick? Maybe with an example!
•  » » » 16 months ago, # ^ |   0 https://codeforces.com/contest/340/submission/89817578Hope this helps :)
•  » » » » 15 months ago, # ^ |   0 Thanks, man!
 » 8 years ago, # |   0 It can be solved with dp using binary search, Here is tutorial.
•  » » 8 years ago, # ^ |   0 I solved it like that
 » 8 years ago, # |   +2 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.
 » 6 years ago, # | ← Rev. 7 →   0 Well, I just solved it using Dijkstra's Algo. Here's the code.It is somewhere near N^2. int d[50001],n,t,maxVal = 0,is[50001]; vector v; int findMax(int i) { queue q; d[i] = 1; q.push(i); is[i] = 1; while (!q.empty()) { int vv = q.front(); q.pop(); is[vv] = 0; for (int j = vv+1; j v[vv] && d[vv]+1 > d[j]) { d[j] = d[vv]+1; maxVal = max(maxVal,d[j]); if (is[j] == 0) { is[j] = 1; q.push(j); } } } } int main() { scanf("%d",&n); for (int i=0;i
•  » » 6 years ago, # ^ |   +7 Simple O(n ^ 2) algorithm is faster than yours.
•  » » » 6 years ago, # ^ |   0 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)
 » 2 years ago, # | ← Rev. 2 →   +3 Here's mine BIT implementation for the same. class Solution { private: void update(int *bit, int n, int idx, int val) { for(; idx <= n; idx += idx & -idx) bit[idx] = max(bit[idx], val); } int query(int *bit, int idx) { int m = 0; for(; idx; idx -= idx & -idx) m = max(m, bit[idx]); return m; } public: int lengthOfLIS(vector& nums) { int n = nums.size(); int bit[n+1] = {0}; vector> p(n); for (int i=0; i