Solving LIS Modified using BIT

#1

I am not clear how to use BIT to solve this problem.Could you give me some more explanation about using BIT to solve this problem.

#3

Let suppose you are at ith position and maximum weighted subsequence ended at that ith position then what you need is previous maximum weighted subsequence weight ended in 0…i-1 th index, if previous maximum weighted subsequence ending is smallest than the current a[i], you need to update maximum subsequence till now but there may be many indices where the elements are smaller than a[i], so all you have to do is to get the maximum of previously maximum ending subsequence using BIT or you can also use segment tree and make up your answer for current index.
You can see the implementation here for better understanding, it’s better if you use a notebook while understanding the code.