色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

一種比線段樹還高效的區間算法

算法與數據結構 ? 來源:小K算法 ? 作者:小K算法 ? 2022-04-11 09:36 ? 次閱讀

01 故事起源

有N個數排列成一排,給定一個區間,如何快速找出區間內最大的數是多少呢?

34f9dfbe-b7a6-11ec-aa7f-dac502259ad0.jpg

02 分析

首先想到的自然是從區間頭開始,依次遍歷完區間內的元素,這樣就可以找出結果了。但這個復雜度是O(n),肯定不是我們想要的。

350a9016-b7a6-11ec-aa7f-dac502259ad0.jpg

再來分析一下有什么特點呢?

這些數不會更改,所以每個區間的結果是不會變的,是否可以把所有的區間結果先計算出來?

3524ef60-b7a6-11ec-aa7f-dac502259ad0.jpg

如果數據規模很小確實可以,一旦數據過大肯定就不行了,因為時間和空間都是O(n^2)。

353e0d1a-b7a6-11ec-aa7f-dac502259ad0.jpg

再考慮一下,區間的最值是有很強的傳遞關系,這就引導我們可以把大問題化為小問題。

355903ea-b7a6-11ec-aa7f-dac502259ad0.jpg

很顯然,這就是一個標準的線段樹模型,不過今天我們再換一個更加高效的算法,稀疏表。 03 稀疏表稀疏表的思想就是提前預處理數據,所以主要針對數據不變的情況,而線段樹更加靈活,可以動態維護數據的變化。

首先還是將區間劃分成很多的小區間。那如何劃分更合理?

第2章節中,我們枚舉了所有的區間情況,可以看出其實有很多重復的情況,比如下面[0,3]其實可以通過[0,1]和[2,3]組合出來。

356cb1c4-b7a6-11ec-aa7f-dac502259ad0.jpg

可以根據長度劃分區間。

設數組為a[i],f[i][j]表示區間[i,j]的最大值。

則長度為1的區間總共有n個,f[i][i]=a[i]。

3584108a-b7a6-11ec-aa7f-dac502259ad0.jpg

長度為2的區間總共有n-1個。

358f1458-b7a6-11ec-aa7f-dac502259ad0.jpg

因為之前已經求出了長度為1的區間的最大值,所以區間長度為2的最大值可以通過區間長度為1的結果直接推出來。

359f34aa-b7a6-11ec-aa7f-dac502259ad0.jpg

接下來就考慮長度為3的區間了嗎?

其實并不是,因為前面已經有了長度為1和2的,所以可以組合出長度為3和4的。

35ae665a-b7a6-11ec-aa7f-dac502259ad0.jpg

那就直接考慮長度為5的嗎?

如果考慮為5的,那你怎么計算呢,前面的也推不出長度為5的結果啊,至少得有3個區間才能推出來

35c94380-b7a6-11ec-aa7f-dac502259ad0.jpg

所以接下來考慮長度為4的區間才是正解,總共有n-3個。

35dd169e-b7a6-11ec-aa7f-dac502259ad0.jpg

再接下來自然就是考慮長度為8的區間了,總共有n-7個。

但這里有個很明顯的問題,就是我們的數組f[i,j]定義的不合理,因為里面很多的小區間沒有用上,比如長度為3,5,6,7等,所以需要重新定義。 04 狀態壓縮可以將第二維用于表示區間長度,第一維表示區間起點,對第二維就可以進行狀態壓縮。

設f[i,j]表示從i開始,長度為2^j的區間的最大值,即區間[i,i+2^j-1]。

35f43f5e-b7a6-11ec-aa7f-dac502259ad0.jpg

則長度為2^j的區間就可以通過左右2個長度為2^(j-1)的區間推出結果。時間和空間的復雜度都為O(nlogn)。

3609f2ea-b7a6-11ec-aa7f-dac502259ad0.jpg

05 區間分解

那查詢結果的時候要怎么處理呢,我們只計算了長度為2^j的區間,并沒有計算長度為3、5、7等區間的結果。

所以這個處理和線段樹的思想也類似,需要進行區間分解。不過線段樹可能分解成很多個區間,而稀疏表只需要分解成2個區間就可以了。

對于任意區間[a,b],長度為b-a+1,總可以找到2個長度為2^j的區間,這2個區間組合起來可以完全覆蓋[a,b],其中j的值為log(b-a+1)。

左邊的區間左端點從a開始,長度為2^j,即區間[a,a+2^j-1]。右邊的區間右端點從b開始,長度為2^j,即區間[b-2^j+1,b]。

則區間[a,b]的最大值就是這兩個區間中更大的那個,即max(f[a,j],f[b-2^j+1,j])。

36223a6c-b7a6-11ec-aa7f-dac502259ad0.jpg

06 代碼實現

代碼實現了最大值和最小值的獲取。

6.1變量定義

int high[50000][17], low[50000][17], n, q;

6.1預處理

void solve() {

// 枚舉區間長度,2^j《=n

for (int j = 1; (1 《《 j) 《= n; ++j) {

// 枚舉左端點i,右端點i+2^j-1《=n-1

for (int i = 0; i + (1 《《 j) 《= n; ++i) {

high[i][j] = max(high[i][j - 1], high[i + (1 《《 (j - 1))][j - 1]);

low[i][j] = min(low[i][j - 1], low[i + (1 《《 (j - 1))][j - 1]);

}

} }

6.1main函數

int main() {

cin 》》 n 》》 q;

for (int i = 0; i 《 n; ++i) {

cin 》》 high[i][0];

low[i][0] = high[i][0];

}

solve();

for (int i = 0; i 《 q; ++i) {

int a, b;

cin 》》 a 》》 b;

a--;

b--;

int j = (int) (log(b - a + 1.0) / log(2.0));

int minHeight = min(low[a][j], low[b - (1 《《 j) + 1][j]);

int maxHeight = max(high[a][j], high[b - (1 《《 j) + 1][j]);

cout 《《 maxHeight - minHeight 《《 endl;

}

return 0; }

07 總結

對于數據不變的情況,可以用稀疏表預處理,這種屬于離線算法。如果要動態維護變化,動態查詢,那就得用在線算法,比如線段樹。但稀疏表的效率確實高,有狀態壓縮和動態規劃的思想,值得深入研究學習。

--- EOF ---

審核編輯 :李倩

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 算法
    +關注

    關注

    23

    文章

    4608

    瀏覽量

    92844
  • 函數
    +關注

    關注

    3

    文章

    4329

    瀏覽量

    62575

原文標題:一種比線段樹還高效的區間算法

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    一種新型高效率的服務器電源系統

    一種新型高效率的服務器電源系統
    發表于 12-19 16:45 ?1次下載

    一種混合顏料光譜分區間識別方法

    古代彩繪顏料的分析是科技考古與文物保護研究的重要內容,高光譜是近年來發展迅速的新興技術,在物質識別上具有廣泛應用,提出一種基于高光譜分區間的混合顏料識別方法。 一種混合顏料光譜分區間
    的頭像 發表于 12-02 16:22 ?70次閱讀
    <b class='flag-5'>一種</b>混合顏料光譜分<b class='flag-5'>區間</b>識別方法

    【「從算法到電路—數字芯片算法的電路實現」閱讀體驗】+本介紹基礎硬件算法模塊實現的好書

    看下本書內容簡介,然后再瀏覽下各個章節的內容。 從簡介來看,本書也是關注最基礎,最常用的那部分算法的電路實現,比較貼合工程實踐,適合無基礎或者有定基礎的線工程人員閱讀。內容選擇是貼合實踐
    發表于 11-20 13:42

    華納云:Chord算法如何管理節點間的聯系?

    Chord算法一種分布式哈希表(DHT)協議,它通過構建個環狀結構來管理節點間的聯系。以下是Chord算法如何管理節點間聯系的具體方式: 環狀結構: Chord
    發表于 11-08 16:03

    一種基于深度學習的二維拉曼光譜算法

    近日,天津大學精密儀器與光電子工程學院的光子芯片實驗室提出了一種基于深度學習的二維拉曼光譜算法,成果以“Rapid and accurate bacteria identification
    的頭像 發表于 11-07 09:08 ?199次閱讀
    <b class='flag-5'>一種</b>基于深度學習的二維拉曼光譜<b class='flag-5'>算法</b>

    一種簡單高效配置FPGA的方法

    本文描述了一種簡單高效配置FPGA的方法,該方法利用微處理器從串行外圍接口(SPI)閃存配置FPGA設備。這種方法減少了硬件組件、板空間和成本。
    的頭像 發表于 10-24 14:57 ?559次閱讀
    <b class='flag-5'>一種</b>簡單<b class='flag-5'>高效</b>配置FPGA的方法

    Huffman壓縮算法概述和詳細流程

    Huffman壓縮算法一種基于字符出現頻率的編碼算法,通過構建Huffman,將出現頻率高的字符用短編碼表示,出現頻率低的字符用長編碼表示,從而實現對數據的壓縮。
    的頭像 發表于 10-21 13:48 ?240次閱讀

    什么是默克爾(Merkle Tree)?如何計算默克爾根?

    01 默克爾的概念 默克爾(Merkle Tree)是一種特殊的二叉,它的每個節點都存儲了個數據塊的哈希值。哈希值是
    的頭像 發表于 09-30 18:22 ?845次閱讀
    什么是默克爾<b class='flag-5'>樹</b>(Merkle Tree)?如何計算默克爾根?

    一種完全分布式的點線協同視覺慣性導航系統

    在本文中,我們提出了一種完全分布式的點線協同視覺慣性導航系統。我們通過蒙特卡羅模擬和真實環境數據集,在稠密特征或稀疏特征環境下將所提出的算法與其他四算法進行了比較。所有結果表明,我們
    的頭像 發表于 09-30 14:45 ?387次閱讀
    <b class='flag-5'>一種</b>完全分布式的點線協同視覺慣性導航系統

    高效精準,電池自動貼面墊機助力鋰電生產 斯特自動化

    斯特自動化自動貼面墊機是一種高效、精準的自動化生產設備,廣泛應用于多個領域,特別是在鋰電池生產、家具制造、建筑裝飾等行業中發揮著重要作用。以下是對自動貼面墊機的詳細介紹:
    的頭像 發表于 07-25 09:56 ?267次閱讀

    rup是一種什么模型

    RUP(Rational Unified Process,統建模語言)是一種軟件開發過程模型,它是一種迭代和增量的軟件開發方法。RUP是由Rational Software公司(現為IBM的
    的頭像 發表于 07-09 10:13 ?1245次閱讀

    基于助聽器開發的一種高效的語音增強神經網絡

    受限的微控制器單元(microcontroller units,MCU)上,內存和計算能力有限。在這項工作中,我們使用模型壓縮技術來彌補這差距。我們在HW上對RNN施加約束,并描述了一種方法來滿足它們
    發表于 06-07 11:29

    請問什么原因導致電流剛關閉e-CAMView軟件的時候還高

    串口打印EnterSpendMode Status = 0x0、喚醒原因 = 0x8 ,這時候電流約80mA左右,請問什么原因導致電流剛關閉e-CAMView軟件的時候還高? 按道理應該小于30ma。怎么能做到進入SuspendMode模式后電流最低?
    發表于 06-03 07:18

    鋰電池般的能量是多少?影響鋰電池能量的因素

    鋰電池作為一種高效的電化學儲能設備,其能量是衡量其性能的關鍵指標之
    的頭像 發表于 04-25 17:03 ?4266次閱讀

    一種高效1.5V/4.2V的LED驅動器電路

    本文介紹了一種高效的 1.5 V 至 4.2 V LED驅動器電路,可與標準鋰離子電池起使用,以增強照明、延長備用電池和延長電池壽命。
    的頭像 發表于 02-25 14:19 ?1162次閱讀
    <b class='flag-5'>一種</b><b class='flag-5'>高效</b>1.5V/4.2V的LED驅動器電路
    主站蜘蛛池模板: 欧美最猛性XXXXX肛交| 成人人观看的免费毛片| 亚洲精品高清视频| 少妇高潮久久久久7777| 乳女教师欲乱动漫无修版动画| 啪啪做羞羞事小黄文| 任你躁国语自产二区在线播放| 青娱国产区在线| 日韩1区1区产品乱码芒果榴莲 | 日本精品久久久久中文字幕2 | 97在线播放| 99在线在线视频观看| 成人国产精品免费网站| 国产AV无码熟妇人妻麻豆 | ewp绞死vk失禁编| 国产爱豆剧果冻传媒在线| 国产亚洲欧美高清在线| 精品视频在线播放| 免费久久狼人香蕉网| 三八成人网| 亚洲伊人久久大香线蕉综合图片| 中文国产乱码在线人妻一区二区| 亚洲午夜性春猛交XXXX| 18日本人XXXXXX18| 欧美特级特黄a大片免费| 污漫日本E同人| 748亚洲大胆国模人体| 成人在线免费观看| 久久精品中文騷妇女内射| 欧美性最猛xxxx在线观看视频| 胸大的姑娘中文字幕视频| 2021国产在线视频| 国产欧美一区二区三区在线看 | 国产午夜亚洲精品一区| 伦理片天堂eeuss影院| 邪恶肉肉全彩色无遮盖| 99热精品在线av播放| 久久AV国产麻豆HD真实| 色婷婷我要去我去也| 99精品国产高清自在线看超| 国产九色在线|