基于線段樹(shù)維護(hù)的上升序列算法的研究與實(shí)現(xiàn)

荊慧

摘要：經(jīng)典的最長(zhǎng)上升子序列算法復(fù)雜度較高，且不適用于序列元素值更改的情況。本文解決的問(wèn)題是經(jīng)典問(wèn)題的變形，在原有問(wèn)題基礎(chǔ)上對(duì)序列值進(jìn)行m次修改，每次修改后求解在原點(diǎn)可以看到幾個(gè)柱子。在經(jīng)典求解最長(zhǎng)上升子序列長(zhǎng)度算法的基礎(chǔ)之上，利用線段樹(shù)對(duì)區(qū)間值進(jìn)行修改、維護(hù)和查詢，求解上述問(wèn)題，將時(shí)間復(fù)雜度降到了[Omlog2n]。

關(guān)鍵詞：最長(zhǎng)上升子序列；上升序列；線段樹(shù)；區(qū)間修改

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）10-0237-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

最長(zhǎng)上升子序列問(wèn)題在計(jì)算機(jī)算法領(lǐng)域是非常經(jīng)典的問(wèn)題，經(jīng)典算法是使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。動(dòng)態(tài)規(guī)劃算法是求解決策過(guò)程的有效最優(yōu)數(shù)學(xué)方法之一，為具有最優(yōu)解結(jié)構(gòu)性質(zhì)的實(shí)際問(wèn)題提供了行之有效的解決方法[1-2]。動(dòng)態(tài)規(guī)劃算法先把原問(wèn)題分解為易于解決的子問(wèn)題，再將子問(wèn)題合并為原問(wèn)題。利用最優(yōu)解性質(zhì)建立的子問(wèn)題最優(yōu)值的遞推關(guān)系可以自底向上遞推地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解，大量降低時(shí)間和空間復(fù)雜度。[3]最長(zhǎng)上升子序列算法不適用于帶修改序列元素的問(wèn)題，且時(shí)間復(fù)雜度較高。本文在經(jīng)典算法的基礎(chǔ)上，對(duì)于經(jīng)典問(wèn)題的變形問(wèn)題，提出了一種更加靈活高效的算法。

1 基于線段樹(shù)查詢修改的上升序列優(yōu)化算法

1.1 問(wèn)題描述

經(jīng)典問(wèn)題描述為：設(shè)A=[a1，a2，a3，…，an]是長(zhǎng)度為n的序列，該序列存在子序列B=[ai1，ai2，ai3，…，ail]，其中滿足條件[ai1

問(wèn)題描述為，已知序列[A=a1，a2，a3，…，an]，A序列初始元素為0，A序列元素代表柱子的高度?？蓪?duì)序列進(jìn)行m次修改，格式為（x，y），意為將第x個(gè)柱子高度修改為y，求解每次修改完成后的在原點(diǎn)可見(jiàn)的柱子個(gè)數(shù)。

1.2 問(wèn)題思路

用線段樹(shù)維護(hù)區(qū)間的序列元素最大值和該區(qū)間內(nèi)最長(zhǎng)上升子序列的長(zhǎng)度。當(dāng)序列元素被修改，直接用普通的線段樹(shù)更新即可；求解上升序列，也可以利用線段樹(shù)查詢更新。可以看出，當(dāng)一個(gè)序列元素值被修改，它只會(huì)對(duì)后面的部分產(chǎn)生影響。利用這個(gè)特性，進(jìn)行線段樹(shù)更新修改。

1.3 問(wèn)題求解

設(shè)Max[rt]為：僅考慮rt所代表的區(qū)間，序列元素的最大值。

設(shè)cnt[rt]為：僅考慮rt所代表的區(qū)間，有多少滿足條件的數(shù) ，即滿足上升序列的長(zhǎng)度。首先，cnt[rt]一定包含它的左子樹(shù)求值結(jié)果cnt[rt*2]； 其次，屬于cnt[rt*2]中的序列元素值可能有比cnt[rt*2+1]中的序列元素值大，那么cnt[rt*2+1]的結(jié)果就會(huì)被cnt[rt*2]的結(jié)果影響，線段樹(shù)區(qū)間合并時(shí)要注意這個(gè)問(wèn)題，重點(diǎn)在于求解被影響后的cnt[rt*2+1]的結(jié)果值。

設(shè) rt*2 代表的區(qū)間中最大高度值為maxn1，將 rt*2+1 所代表的區(qū)間分左右兩個(gè)子樹(shù)，左子樹(shù)區(qū)間中最大高度值為maxn2，進(jìn)行討論：

1） 若maxn1>=maxn2，遞歸判斷右子樹(shù)還多少個(gè)大于maxn1的值。

2） 若maxn1

輸入：序列長(zhǎng)度n和修改序列次數(shù)m，之后給出n行，每行的形式為（x，y），意為將第x個(gè)元素修改為y。

輸出：每次修改后，輸出上升序列的長(zhǎng)度。

1.int x，y，n，m //定義變量

3.scanf（"%d%d"，&n，&m）

4.for i=1 to m do

5.scanf（"%d%d"，&x，&y）

6.change（y，x，1，1，n） //線段樹(shù)更新

7.printf（"%d＼n"，cnt[1]）//整個(gè)序列的最長(zhǎng)上升子序列長(zhǎng)度

從時(shí)間復(fù)雜度來(lái)看，i每次從1循環(huán)到m，由于每次循環(huán)體內(nèi)時(shí)間復(fù)雜度為O（[log2n]），由此可見(jiàn)改進(jìn)后的算法時(shí)間復(fù)雜度為[Omlog2n]。

線段樹(shù)統(tǒng)計(jì)區(qū)間上升序列長(zhǎng)度函數(shù)num：

1.int mid=（left+right）/2

2.if（left==right） then

3.返回maxn

4.if（maxn>=Max[rt*2]） then

5.遞歸返回num（maxn，rt*2+1，mid+1，right）

6.遞歸返回cnt[rt]-cnt[rt*2]+num（maxn，rt*2，left，mid）

線段樹(shù)更新函數(shù)change：

1.int mid=（left+right）/2

2.if（left==right） then

3.cnt[rt]=1

4.Max[rt]=k

5.return返回

6.if（x<=mid） then

7.change（k，x，rt*2，left，mid）

8.if（x>mid） then

9.change（k，x，rt*2+1，mid+1，right）

10.Max[rt]：=max（Max[rt*2]，Max[rt*2+1]）

11.cnt[rt]：=cnt[rt*2]+num（Max[rt*2]，rt*2+1，mid+1，right）

2 兩種算法時(shí)間復(fù)雜度和空間復(fù)雜度的比較

使用經(jīng)典算法解決該問(wèn)題的時(shí)間復(fù)雜度為[Omn2]，空間復(fù)雜度為[On]；

本文算法時(shí)間復(fù)雜度為[Omlog2n]，空間復(fù)雜度為[On]。本文算法將動(dòng)態(tài)規(guī)劃問(wèn)題最優(yōu)子解的性質(zhì)和線段樹(shù)維護(hù)更新的性質(zhì)相結(jié)合，在空間復(fù)雜度差別不大的情況下，將算法復(fù)雜度優(yōu)化到了平方數(shù)量級(jí)以下。

對(duì)序列元素值進(jìn)行m次修改，每次修改元素區(qū)間維護(hù)的時(shí)間復(fù)雜度O（[log2n]）。

3 結(jié)束語(yǔ)

文中探討了基于線段樹(shù)查詢修改的上升序列的變形優(yōu)化問(wèn)題，通過(guò)經(jīng)典算法和本文算法的比較，最終將時(shí)間復(fù)雜度控制在平方數(shù)量級(jí)的范圍內(nèi)，有效地降低了該類問(wèn)題的時(shí)間復(fù)雜度，為后續(xù)的應(yīng)用推廣奠定了基礎(chǔ)。

參考文獻(xiàn)：

[1] Alsuwaiyel MH.Algorithms design techniques and analysis[M].Beijing：Publishing House of Electronics Industry.2003.

[2] Cooper R.Dynamic programming： An overview[EB/OL].2001.http： //econ.bu.edu /faculty /cooper/Dynprog /introlect.pdf.

[3] 郭冬梅.基于狀態(tài)壓縮的最長(zhǎng)公共上升子序列快速算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（05）：40-43.

【通聯(lián)編輯：梁書(shū)】

附錄：①程序C++源代碼

#include

using namespace std；

const int N=400010；

int cnt[N]；

double Max[N]；

int num（double maxn，int rt，int left，int right）

{

int mid=（left+right）/2；

if（left==right）

return maxn

if（maxn>=Max[rt*2]）

return num（maxn，rt*2+1，mid+1，right）；

return cnt[rt]-cnt[rt*2]+num（maxn，rt*2，left，mid）；

}

void change（double k，int x，int rt，int left，int right）

{

int mid=（left+right）/2；

if（left==right）

{

cnt[rt]=1；

Max[rt]=k；

return；

}

if（x<=mid）

change（k，x，rt*2，left，mid）；

else

change（k，x，rt*2+1，mid+1，right）；

Max[rt]=max（Max[rt*2]，Max[rt*2+1]）；

cnt[rt]=cnt[rt*2]+num（Max[rt*2]，rt*2+1，mid+1，right）；

}

int main（）

{

double x，y；

int n，m；

scanf（"%d%d"，&n，&m）；

for（int i=1；i<=m；i++）

{

scanf（"%lf%lf"，&x，&y）；

change（y/x，（int）x，1，1，n）；

printf（"%d＼n"，cnt[1]）；

}

return 0；

}