主頁 >  其他 > 分治與線段樹

分治與線段樹

2020-09-15 09:35:13 其他

  

    線段樹(Segment Tree)也稱區間樹(Interval Tree)、范圍樹(Range Tree)，是一種用于區間資訊的維護與查詢的特殊資料結構，線段樹使用分治思想，將連續區間遞回分解成若干小區間，在處理范圍修改查詢等操作時能夠通過整合小區間的資訊減少運算量從而實作快速修改與查詢，

   

線段樹的構造

     線段樹的主要思想是使用一棵二叉樹(Binary Tree)來存盤整個區間的資訊，其中每個非葉子結點[a,b]表示一個連續區間(Interval)即線段(Segment)，該結點中可存放此區間內的一些整體資訊如區間和、區間最值、區間長度等，它的左子結點[a,(a+b)/2]和右子結點[(a+b)/2+1,b]分別表示該區間的左半區間和右半個區間，線段樹的根節點存放完整區間的資訊，當需要修改或查詢區間內容時，從根結點向下遞回，若當前結點完全被操作區間覆寫，則將該結點資訊向上傳遞，同時該結點不再向下遞回；若當前結點被操作區間覆寫一部分，則向對應的子樹進行遞回直到某結點被操作區間覆寫，圖中給出了有十個元素的線段樹劃分示例，

 

    從圖中可以看出，線段樹是一種二叉平衡樹，記為T[a,b]，引數a,b表示區間[a,b]，其中b-a稱為區間的長度L，則線段樹T[a,b]可遞回定義:

        ①若L>1，則T[a,(a+b)/2]為T的左子樹，T[(a+b)/2+1,b]為T的右子樹，

        ②若L=1，則T為葉子結點，

     線段樹的平分構造其實是利用了二分的方法，若根節點為T[a,b]，那么它的深度為h=log2(b-a+1)+1（向上取整）,假定根結點的長度L=2h，不難發現，第i層有2i個結點，每個結點對應一個2h-i的區間，結點總數為2h+1-1，略小于區間長度的2倍，當區間長度不為2的整數冪時，仍滿足上述結論，

   

    線段樹可以通過遞回進行建樹，具體思想是利用分治法，從根結點開始遞回建樹，訪問一個結點時，先判斷當前結點是否為葉子結點，若是葉子結點，則將區間對應元素賦值給該結點的區間和、最值等元素；若當前結點不是葉子結點，則分別遞回構造它的左子樹和右子樹，構造結束后，合并兩子樹的區間和、最值等元素，

為了在后續維護線段樹的程序中降低運行時間，在結點中保存一個懶惰標記sign，懶惰標記的使用方法將在后續內容中詳解，演算法1.1給出了線段樹的結點定義及建樹程序實作方法，

【演算法 1.1】線段樹建樹

template <class T>
class SegmentTree{//線段樹類定義
public:
    int L,R;//存放左右端點
    T sum,minv,maxv;//存放區間和最大值最小值
    T sign;//懶惰標記
    void Init(T a)//結點初始化函式
    {
        sum=minv=maxv=a;
        sign=0;
    }
};
template <class T>
void BuildTree(SegmentTree<T> Tree[],int a[],int o,int l,int r)
{//Tree代表線段樹陣列，a為元素陣列，o為當前結點下標，l,r為區間范圍
    if(l>r)return;//左端點大于右端點，引數有錯
    Tree[o].L=l;//初始化結點區間
    Tree[o].R=r;
    if(l==r)Tree[o].Init(a[l]);//若當前結點為葉子結點則賦初值
    else
    {
        int mid=(l+r)/2;//取當前區間中點
        BuildTree(Tree,a,o+o,l,mid);//遞回構建左右子樹
        BuildTree(Tree,a,o+o+1,mid+1,r);
        PushUp(Tree,o);//合并子樹資訊
    }
}

    演算法1.1使用陣列存放線段樹，根據二叉樹的性質，當前元素的左孩子下標Ol為當前結點下標O的2倍，Ol=2O，右孩子下標為Or=2O+1，也可以使用指標來存放左右子樹，

   分析線段樹的建樹程序可知，每次遞回向下將陣列分解成大致相等的兩部分，分解只需要單位時間即可完成，在向上合并的程序中也需要單位時間來合并，因此可推導線段樹建樹遞回式: T(n)=2T(n/2)+O(1)

    線段樹的結點數略小于陣列長度的2倍，因此空間復雜度為O(n)，

   

RMQ問題

    區間最值(Range minimum query)問題即RMQ問題可使用線段樹快速解決，具體實作思路為：當查詢區間[L,R]的最值時，從線段樹的根結點向子樹遞回尋找，若當前結點被查詢區間覆寫一部分，則向對應子樹遞回；若當前結點被查詢區間完全覆寫，則將當前結點保存的最值回傳給上一層，向上合并的程序中通過比較兩子樹回傳的最值確定當前結點的回傳值，不斷向上合并直到根結點回傳最終結果，下圖給出了查詢[4,6]區間內最值的遞回樹，

   

 

    分析上圖的查詢遞回樹可看出查詢程序中會遇到三種情況：

        ①查詢區間與當前結點左區間有交集，需要向左子樹遞回查詢，

        ②查詢區間與當前結點右區間有交集，需要向右子樹遞回查詢，

        ③當前結點代表的區間全部位于查詢區間內部，此時直接回傳當前區間最值，不再向下遞回，

    對上述三種情況的處理方法非常重要，是線段樹的核心思想之一，在查詢、修改、插入和洗掉操作中都要用到，綜合線段樹查詢最值的思想與需要注意的情況，不難寫出線段樹的RMQ演算法，

【演算法 1.2】線段樹區間最小值查詢

template <class T>
T RMQmin(SegmentTree<T> Tree[],int o,int l,int r)
{
    if(l<=Tree[o].L&&r>=Tree[o].R)//若當前結點范圍被查詢區間覆寫
    {
        PushUp(Tree,o);//更新該結點資訊
        return Tree[o].minv;//回傳當前區間最小值
    }
    else
    {
        int mid=(Tree[o].L+Tree[o].R)/2;//取當前區間中點
        T minx,min1,min2;//保存最小值
        min1=min2=MAXV;//初始化為最大值
        if(l<=mid)min1=RMQmin(Tree,o+o,l,r);//左子區間與操作區間有交集
        if(r>mid)min2=RMQmin(Tree,o+o+1,l,r);//右子區間與操作區間有交集
        minx=(min1<min2?min1:min2);//比較子樹的回傳值，選出區間最小值
        PushUp(Tree,o);//更新結點
        return minx;//回傳當前區間最小值
    }
}

 

    分析演算法及圖可以發現，雖然查詢程序中有分叉，但是每層最多只有2個結點向下延伸，因此遞回查詢訪問的結點總數不超過2h，這實際上是將帶查詢線段分解成不超過2h個不相交線段的并集，因此查詢所需的時間為:O(log n)

懶惰標記

    區間修改需要用到懶惰標記，懶惰標記的處理方法是線段樹能夠快速修改區間元素的關鍵思想，

    分析線段樹的特點不難發現，任意區間都可以被線段樹中不超過2h個結點表示，若需要將某一區間的值增加x，可以只修改這不超過2h個結點，為此引入一個懶惰標記sign來記錄結點需要改變的量，若某一結點懶惰標記改變了x，說明該結點表示區間[l,r]內所有值都應改變x，此時需要將該結點的最值改變x，區間和改變(r-l+1)，仔細分析不難發現，若將區間和與最值資訊全部改變，表明該區間已完成修改，不再需要懶惰標記，此時可將sign置零，但該結點的子區間尚未更改，若下次查詢時訪問了子區間會導致結果出錯，

   

    考慮到后續可能的查詢操作，不妨將修改懶惰標記的操作隨查詢操作一起執行保證正確性，由于查詢操作是自頂向下的，因此可以攜帶祖先結點的懶惰標記給當前結點，根據當前查詢操作是否需要訪問子樹來決定是否要將懶惰標記繼續下放，當無需再下放懶惰標記時，可更新該結點并逐步更新它的祖先結點，結合剛才的結論不難發現，當懶惰標記下放給子樹并計算完畢后，準確的區間資訊能夠通過調取子樹資訊來整合，此時可將sign置零，視為失去懶惰標記，

    由于修改操作也需要查詢來確定修改結點的位置，因此修改時向下遞回的程序也可視為查詢操作，當修改操作需要訪問當前結點的子樹時，當前結點視作得到懶惰標記后又失去懶惰標記，對應的子樹則獲得懶惰標記，根據這個規則遞回下去，直到某一結點的子樹不被訪問，該結點保留懶惰標記，

    綜合上述結論，總結結點懶惰標記變化情況，設修改或查詢區間為[p,q]，當前結點表示區間為[l,r]，改變值為x：

        ①當前結點被修改操作訪問，且修改區間[p,q]完全覆寫當前結點表示區間[l,r]，獲得懶惰標記x，

        ②當前結點被修改操作訪問，且修改區間[p,q]與左子樹[l,(l+r)/2]有交集，此時向左子樹遞回，待遞回回傳后，區間和改變x(q-(l+r)/2+1)，

        ③當前結點被修改操作訪問，且修改區間[p,q]與右子樹[(l+r)/2+1,r]有交集，此時向右子樹遞回，待遞回回傳后，區間和改變x((l+r)/2+1-p+1)，

        ④當前結點被查詢操作訪問，失去懶惰標記，區間和改變x(r-l+1)，

    分析上述四種情況，可發現②③可能同時發生，這時左右子樹都會被訪問，

    上述情況沒有給出修改最值的操作，主要原因是若獲得懶惰標記的情況為②、③時區間最值的更新情況不確定，需要遞回到最深層后才能逐步回傳準確的最值資訊，因此應設定一個整合操作放在回傳操作之前，保證區間最值的正確性，

    現在已經解決了懶惰標記獲得和失去的情況以及修改結點資訊的步驟，修改與查詢的程序中，參照上述四個情況與資訊修改方法即可保證查詢回傳結果的正確性，下圖給出了將區間[3,9]內所有元素值增加1后懶惰標記的保留情況，

 

    修改操作從根結點開始，向下遞回修改結點，其詳細操作程序如下：

       （1）訪問[1,10]，修改[3,9]屬于情況②③

       （2）訪問[1,5]，修改[3,5]屬于情況②③

       （3）訪問[1,3]，修改[3,3]屬于情況③

       （4）訪問[3,3]，修改[3,3]屬于情況①，保留懶惰標記

       （5）[3,3]更新區間資訊回傳給[1,3]，[1,3]更新區間資訊回傳給[1,5]

       （6）訪問[4,5]，修改[4,5]屬于情況①，保留懶惰標記

       （7）[4,5]更新區間資訊回傳給[1,5]，[1,5]更新區間資訊回傳給[1,10]

       （8）訪問[6,10]，修改[6,9]屬于情況②③

       （9）訪問[6,8]，修改[6,8]屬于情況①，保留懶惰標記

       （10）[6,8]更新區間資訊回傳給[6,10]

       （11）訪問[9,10]，修改[9,9]屬于情況②

       （12）訪問[9,9]，修改[9,9]屬于情況①，保留懶惰標記

       （13）[9,9]更新區間資訊回傳給[9,10]，[9,10]更新區間資訊回傳給[6,10]，[6,10]更新區間資訊回傳給[1,10]，[1,10]更新區間資訊

仔細觀察可發現修改操作結束后，保留懶惰標記的結點區間的并集與修改區間一致，下面給出了懶惰結點下放步驟的演算法1.3，由于最值等資訊需要等到遞回回傳時才能獲得準確資訊，因此下放操作沒有其他計算步驟：

 【演算法 1.3】懶惰標記下放

void PushDown(SegmentTree<T> Tree[],int o)//懶惰標記下放，o為當前結點
{
    if(Tree[o].L<Tree[o].R)//若當前結點不是葉子結點，下放懶惰標記
    {
        Tree[o+o].sign+=Tree[o].sign;
        Tree[o+o+1].sign+=Tree[o].sign;
        Tree[o].sign=0;
    }
    else Tree[o].sign=0;//若當前結點是葉子結點，無需下放標記直接置零
}

分析整合區間資訊程序，給出演算法1.4：

【演算法 1.4】區間資訊整合

template <class T>
void PushUp(SegmentTree<T> Tree[],int o)//整合函式，o為當前結點
{
    int lc=o*2,rc=o*2+1;//記錄左右子樹
    if(Tree[o].L<Tree[o].R)//若當前結點不是葉子結點，重整當前結點資訊
    {
        Tree[o].sum=Tree[lc].sum+Tree[rc].sum;
        Tree[o].minv=(Tree[lc].minv<Tree[rc].minv?Tree[lc].minv:Tree[rc].minv);
        Tree[o].maxv=(Tree[lc].maxv>Tree[rc].maxv?Tree[lc].maxv:Tree[rc].maxv);
    }
    if(Tree[o].sign!=0)//若懶惰標記不為0，更新資訊
    {
        Tree[o].sum+=Tree[o].sign*(Tree[o].R-Tree[o].L+1);
        Tree[o].minv+=Tree[o].sign;
        Tree[o].maxv+=Tree[o].sign;
        PushDown(Tree,o);//更新結束即可下放懶惰標記
    }
}

    合并與下放僅需做有限次操作，且都能在單位時間內完成，

區間修改與查詢

    參考下圖并綜合之前的結論，使用演算法1.3與演算法1.4作為輔助函式，給出線段樹區間修改的演算法1.5：

【演算法 1.5】線段樹區間修改

template <class T>
void Modify(SegmentTree<T> Tree[],int o,int l,int r,int x)
{//[l,r]區間內所有元素增加x
    if(l<=Tree[o].L&&r>=Tree[o].R)//若當前結點被修改區間覆寫
    {
        Tree[o].sign+=x;//更新當前結點懶惰標記
        PushUp(Tree,o);//重整該結點資訊
        return;//不再向下遞回
    }
    else
    { //若當前結點不被操作區間覆寫
        PushDown(Tree,o);//視為訪問該結點，下放懶惰標記
        int mid=(Tree[o].L+Tree[o].R)/2;//取當前區間中點
        if(l<=mid)Modify(Tree,o+o,l,r,x);//左子區間與操作區間有交集
        if(r>mid)Modify(Tree,o+o+1,l,r,x);//右子區間與操作區間有交集
        PushUp(Tree,o);//更新當前結點
    }
}

    除了演算法1.5所描述的將區間改變x的情況外，還有將區間置為某一數值的操作，這時一個懶惰標記已不能滿足需求，此時可引入另一對懶惰標記flag與sign2，用flag表示該區間是否需要設定為某一值，sign2用來存盤設定的值，在修改區間資訊時要先判斷flag，若不需要重設區間，再判斷sign是否需要改動區間，設定操作與修改操作非常相似，修改操作是改變sign值，而設定操作是將flag置為真，再設定sign2，為了滿足設定操作的需求，在PushUp和PushDown函式中各加入一個判斷flag是否為真并修改區間的操作即可，設定區間與修改區間的演算法極為相似，僅有幾行改動，因此不再給出具體實作，

    區間和查詢需要注意處理如何向子區間遞回以及處理子區間回傳值的方法，與RMQ問題相似，需要考慮四種情況，結合演算法1.2，給出線段樹查詢區間和的演算法1.6:

【演算法 1.6】線段樹區間查詢

template <class T>
T InternalSum(SegmentTree<T> Tree[],int o,int l,int r)
{
    if(l<=Tree[o].L&&r>=Tree[o].R)
    {//若當前區間在查詢區間之內，更新資訊回傳當前區間和
        PushUp(Tree,o);
        return Tree[o].sum;
    }
    else
    {//若當前區間不在查詢區間內
        PushDown(Tree,o);//懶惰標記下放
        T sum=0;//保存回傳的區間和
        int mid=(Tree[o].L+Tree[o].R)/2;
        if(l<=mid)sum+=InternalSum(Tree,o+o,l,r);//左子區間包含查詢區間
if(r>mid)sum+=InternalSum(Tree,o+o+1,l,r);//右子區間包含查詢區間
        PushUp(Tree,o);//更新結點資訊
        return sum;//回傳當前區間和
    }
}

    分析演算法1.5與1.6可知修改與查詢的結點不多于2h，訪問結點不多于4h，這與演算法1.2僅存在常數項的差別，因此可直接推匯出線段樹區間修改的時間復雜度為O(log n)，

    除了查詢與修改操作外，線段樹還可進行批量插入與洗掉操作，與修改查詢操作思路相似，引入一對新的懶惰標記，表示是否需要插入洗掉，以及插入洗掉后該結點表示區間的偏移量，同時結點子區間的分界點不能再通過去中點的方式而是用特定值存盤，插入操作會影響線段樹的平衡性，若插入m個元素，那么該線段樹的深度h就會增加g=log2(m)，這時最好使用指標來存盤子樹，否則存盤開銷將會增加2g，可考慮借鑒AVL樹的思想進行優化，

線段樹在演算法競賽中的應用

    線段樹的應用非常廣泛，區間修改查詢等操作在統計類問題中非常常見，在計算幾何中，通過線段樹套用來表示二維三維空間，可以實作對幾何元素進行快速移動修改等操作，此外線段樹還可用于對記憶體的高效管理等，

ACM/ICPC Asia-Nanjing 2007

題目鏈接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=22&problem=1939&mosmsg=Submission+received+with+ID+2539428

    After doing Ray a great favor to collect sticks for Ray, Poor Neal becomes very hungry. In return for Neal’s help, Ray makes a great dinner for Neal. When it is time for dinner, Ray arranges all the dishes he makes in a single line (actually this line is very long, the dishes are represented by 1, 2, 3...).You make me work hard and don’t pay me! You refuse to teach me Latin Dance! Now it is time for you to serve me", Neal says to himself.
    Every dish has its own value represented by an integer whose absolute value is less than 1,000,000,000.Before having dinner, Neal is wondering about the total value of the dishes he will eat. So he raisesmany questions about the values of dishes he would have.
    For each question Neal asks, he will first write down an interval [a; b] (inclusive) to represent allthe dishes a,a+ 1,...,b, where aand bare positive integers, and then asks Ray which sequence of consecutive dishes in the interval has the most total value. Now Ray needs your help.
Input
    The input file contains multiple test cases. For each test case, there are two integers nand min the first line (n; m < 500000). n is the number of dishes and mis the number of questions Neal asks.
    Then n numbers come in the second line, which are the values of the dishes from left to right. Next m lines are the questions and each line contains two numbers a, b as described above. Proceed to the end of the input file.
Output
    For each test case, output m lines. Each line contains two numbers, indicating the beginning position and end position of the sequence. If there are multiple solutions, output the one with the smallest beginning position. If there are still multiple solutions then, just output the one with the smallest end position. Please output the result as in the Sample Output.
Sample Input
3 1
1 2 3
1 1
Sample Output
Case 1:
1 1

【分析】

    該題目實際上是求解動態最大連續和問題，此類問題有多種解法，其中動態規劃法與分治法結合的演算法較為實用，該方法解決最大連續和問題分為如下步驟：

       （1）分解：將問題分解為大致相等的兩個字問題，遞回分解直到不可再分

       （2）處理：對每個子問題，存盤它的區間和sum，最大連續和Nmax及其起始Nmaxs和結束位置Nmaxe，左端最大連續和Lmax及其結束位置Lmaxe，右端最大連續和Rmax及其開始位置Rmaxs，

       （3）合并：若當前結點為葉子結點，其存盤的所有和為該結點元素值，所有位置為該結點位置；若當前結點為非葉子結點，最大連續和Nmax為左子結點的最大連續和NmaxL、右端最大連續和RmaxL與其右子結點的最大連續和NmaxR、左端最大連續和LmaxR相組合的狀態轉移方程：Nmax=(NmaxL,NmaxR,RmaxL+LmaxR)，剩余兩個連續和狀態轉移方程與之相似，根據各方程的結果修改對應位置值，

    分析該解法可發現每個結點都會被處理一次，而結點總數為2n-1，因此查詢時間開銷為，該方法僅適用于靜態連續最大和，若查詢區間為動態的，每次查詢都將重復計算，n次查詢時間復雜度為O(n2)，

    結合線段樹相關理論不難發現，分解程序即是線段樹建樹程序；處理方法通過增加結點存盤元素即可；合并程序修改PushUp函式即可完成，

    根據上述思路修改線段樹，給出題目的實作方法 程式1.1

【程式1.1】動態連續最大和

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=500005;//最大盤子數
class Tree{ //線段樹
public:
    long long sum,Nmax,Lmax,Rmax;//區間和等和元素
    int Nmaxs,Nmaxe,Lmaxe,Rmaxs;//各區間和端點
    int l,r;//區間范圍
    void eq(Tree a)//賦值函式
    {
        sum=a.sum;Nmax=a.Nmax;Lmax=a.Lmax;Rmax=a.Rmax;
        Nmaxs=a.Nmaxs;Nmaxe=a.Nmaxe;Lmaxe=a.Lmaxe;Rmaxs=a.Rmaxs;
        l=a.l;r=a.r;
    }
};
void PushUp(Tree &o,Tree &l,Tree &r)//整合函式
{
    if(o.l<o.r)//若當前結點不是葉子結點
    {
        o.l=l.l;o.r=r.r;
        o.sum=l.sum+r.sum;//求區間和
        if(l.sum+r.Lmax>l.Lmax)//求左端最大連續和及其端點
        {
            o.Lmax=l.sum+r.Lmax;
            o.Lmaxe=r.Lmaxe;
        }
        else
        {
            o.Lmax=l.Lmax;
            o.Lmaxe=l.Lmaxe;
        }
        if(r.sum+l.Rmax>=r.Rmax)//求有段最大連續和及其端點
        {
            o.Rmax=r.sum+l.Rmax;
            o.Rmaxs=l.Rmaxs;
        }
        else
        {
            o.Rmax=r.Rmax;
            o.Rmaxs=r.Rmaxs;
        }
        if(l.Nmax>=r.Nmax)//求最大連續和及其端點
        {
            o.Nmax=l.Nmax;
            o.Nmaxs=l.Nmaxs;
            o.Nmaxe=l.Nmaxe;
        }
        else
        {
            o.Nmax=r.Nmax;
            o.Nmaxs=r.Nmaxs;
            o.Nmaxe=r.Nmaxe;
        }
        if(o.Nmax<=l.Rmax+r.Lmax)
        {
            if(o.Nmax==l.Rmax+r.Lmax)//題目要求區間盡量靠前
            {
                if(o.Nmaxs<l.Rmaxs)return;
                if(o.Nmaxs==l.Rmaxs&&o.Nmaxe<r.Lmaxe)return;
            }
            o.Nmax=l.Rmax+r.Lmax;
            o.Nmaxs=l.Rmaxs;
            o.Nmaxe=r.Lmaxe;
        }
    }
}
void Build(Tree T[],long long a[],int o,int l,int r)
{//線段樹構建函式
    if(l>r)return;
    T[o].l=l;T[o].r=r;
    if(l==r)
    {
        T[o].sum=T[o].Nmax=T[o].Lmax=T[o].Rmax=a[l];
        T[o].Nmaxs=T[o].Nmaxe=T[o].Lmaxe=T[o].Rmaxs=l;
        return;
    }
    int mid=(l+r)/2;
    Build(T,a,o+o,l,mid);
    Build(T,a,o+o+1,mid+1,r);
    PushUp(T[o],T[o+o],T[o+o+1]);
    return;
}
Tree query(Tree T[],int o,int l,int r)
{//查詢函式
    if((l<=(T[o].l))&&(r>=(T[o].r)))return T[o];
    int mid=(T[o].l+T[o].r)/2;
    Tree a,b,c;
    int fa=0,fb=0;
    if(l<=mid){fa=1;a.eq(query(T,o+o,l,r));}
    if(r>mid){fb=1;b.eq(query(T,o+o+1,l,r));}
    if(fa&&fb){c.l=a.l;c.r=b.r;PushUp(c,a,b);}
    else if(fa)c.eq(a);
    else c.eq(b);
    return c;
}
Tree t[4*maxn];
long long a[maxn];
int main()
{
    int n,m;
    int ca=1;
    int l,r;
    Tree T;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        Build(t,a,1,1,n);
        printf("Case %d:\n", ca++) ;
        while(m--) {
            scanf("%d%d",&l,&r);
            T.eq(query(t,1,l,r));
            printf("%d %d\n",T.Nmaxs,T.Nmaxe) ;
        }
    }
    return 0;
}

    由于各結點保存了區間資訊，查詢時只需整合不超過線段樹深度4倍的結點即可完成運算，時間復雜度為O(log n)，

    分治演算法不僅在常見的排序查找演算法中有廣泛應用，對于特定的數學問題也是不可或缺的處理手段，同時在一些資料結構與并行運算模型中也要用到分治思想，是演算法設計中最重要的思想之一，仍有許多未知的道路需要探索，

【未經允許 禁止轉載】

   

 

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/45349.html

標籤：其他

上一篇：拓展歐幾里得

下一篇：劍指Offer(第二版)面試題目分析與實作-解決面試題的思路

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂