树状数组优化dp

权值树状数组优化LIS问题。

LIS的权值树状数组O(nlogn)O(n\log n)做法

可能需要的前置知识:

  • O(n2)O(n^2)的dp做法。
  • 树状数组的概念,更新和查找前缀的操作。
  • 听说过权值线段树/权值树状数组这种思想/操作。
  • 离散化(本题还用不到)

对于传统的LIS问题,我们可以设dp[i]dp[i]表示以第ii个元素结尾且单增的子序列组成的集合中,序列最长的长度。考虑其能由哪些状态转移过来,容易发现,dp[1...n1]dp[1...n - 1]中有一部分可以更新dp[i]dp[i]的值,我们的状态转移方程是:dp[i]=max(dp[j]+1)dp[i] = max(dp[j] + 1),其中 1j<i\ 1 \leq j < ia[j]<a[i]a[j] < a[i] 。暴力每次O(n)O(n)的转移消耗无法应对10510^5这样的数据范围,这个时候我们可以一个很自然的想法是想办法加速转移过程。

我们先想一下为啥刚才我们一下子没想到很快的优化方法,原因在于,能够转移到dp[i]dp[i]状态的其他状态,是前缀,又不完全是前缀。1j<i1\leq j < i表明其确实是前缀的一部分,但是a[j]<a[i]a[j] < a[i]的限制似乎使得我们必须暴力甄别出到底哪些dp[j]dp[j]能够更新dp[i]dp[i]。我们的希望是:如果a[j]<a[i]a[j] < a[i]1j<i1\leq j <i能够共同综合出一个新的“顺序”,同时满足这两个条件的元素是一个“前缀”就好了。这个时候,如果之前接触过“权值线段树/权值树状数组(值域线段树/值域树状数组)”(即把值作为下标,把值出现的次数作为该下标处存储的内容,即权值,或者你也可以存一些其他你关心的内容,根据题目不同而不同)这个概念的话,可能会想到这个玩意儿可以同时按照“顺序”和“大小”两个限制去维护元素集的属性。做法是,往数据结构中插入元素的时候,不是按照这个元素在原始数组中的下标去插入,而是这个元素的值是多少我们就把它插到哪个位置。这样的话,我们按照原始数组顺序遍历元素的时候,先查一下数据结构中比当前元素小的部分,就能查到比它小还比它靠前的元素的一些属性,然后把当前元素再插入到数据结构中,以此来维护数据结构。(以元素大小为数据结构中的“下标”)基于权值使用数据结构的话,一般要考虑值域过大空间不足的情况,遇到这种情况可能要做离散化。