HekpoMaH's blog

By HekpoMaH, 7 years ago, In English

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 :)

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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:)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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. :]

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Can you give a code example cuz i still dont understand in :(

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 2   Vote: I like it +4 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          using segment tree: 4386727

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            @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.

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            @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?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        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.
        
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                oh sorry :) i misunderstood.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                  Rev. 3   Vote: I like it +4 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +9 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks 1 more time

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
5 years ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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<int> v;

int findMax(int i) {
    queue<int> 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<n; j++) 
        if (v[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<n;i++) { scanf("%d",&t); v.pb(t); }
    f(i,n) findMax(i);
    printf("%d",maxVal);
}
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

»
11 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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<int>& nums) {
        int n = nums.size();
        int bit[n+1] = {0};
        vector<pair<int, int>> p(n);
        for (int i=0; i<n; i++) p[i] = make_pair(nums[i], -(i+1));
        sort(p.begin(), p.end());
        for (int i=0; i<n; i++) update(bit, n, -p[i].second, query(bit, n, -p[i].second) + 1);
        return query(bit, n);
    }
};