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

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

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.

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);
}

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);
    }
};