用于动态改变具有最长子序列长度查询的n长度序列的数据结构

Question

我需要n使用以下方法设计保持长度序列的数据结构:

• increasing() - 返回最长的子序列的长度
• change(i, x) - 将x添加到序列的第i个元素

直观地说,这听起来像某种间隔树可解决的东西.但我不知道该怎么想.

我想知道如何使用这个事实,我们完全不需要知道这个子序列是怎样的,我们只需要它的长度......

也许这是可以使用的东西,但我现在几乎陷入困境.

Answer 1

LIS可以用树来解决，但还有另一种用动态规划的实现，它比递归树更快。这是一个简单的 C++ 实现。

class LIS {
    private vector<int> seq ;
    public LIS(vector<int> _seq) {seq = _seq ;}
    public int increasing() {
        int i, j ;
        vector<int> lengths ;
        lengths.resize(seq.size()) ;
        for(i=0;i<seq.size();i++) lengths[i] = 1 ;

        for(i=1;i<seq.size();i++) {
            for(j=0;j<i;j++) {
                if( seq[i] > seq[j] && lengths[i] < lengths[j]+1 ) {
                    lengths[i] = lengths[j] + 1 ;
                }
            }
        }

        int mxx = 0 ;
        for(i=0;i<seq.size();i++)
            mxx = mxx < lengths[i] ? lengths[i] : mxx ;

        return mxx ;
    }

    public void change(i, x) {
        seq[i] += x ;
    }

}