子陣查詢

Question

所以我試圖解決這個編程問題。給定一個數組和一些查詢的數組。每個查詢都會給出三個數字a，b，c，並要求您回答從索引a到索引b（均包括在內）中小於或等於c的所有元素的總和。

例如：

鑑於陣列：{2,4,6,1,5,1,6,4,5,4}

3個查詢被回答：

2 4 4 - > ANS = 5即{4 + 1}

1 5 3 - > ANS = 3即{2 + 1}

4 5 1 - > ANS = 1

每個

在陣列中的值小於10^5，陣列長度和查詢次數可以高達10^5

這是我所做的我用莫氏算法（平方根分解）對查詢進行排序，並創建一個二進制索引樹，用於存儲元素累積和小於1-10^5中所有值的元素，並使更新從查詢移動到查詢。使用這種算法，我的解決方案的總體複雜度爲O（q * sqrt（N）* log（N）），但速度不夠快。我正在尋找更好的算法。我認爲查詢的平方根分解不起作用。有沒有更好的算法來解決這個問題？

我想知道如果一些數據結構可以解決這個問題，我不知道？

Answer 1

你可以反過來分解它。即建立一個半陣列樹（這是（n log n）space）。對每個子數組進行排序併爲其構建累積和數組。現在，你的查詢都是（日誌 ñ）各（日誌ñ識別子陣列和其他日誌ň找到每個子陣列的累計總和）。

例如，如果你原來的數組是

  5,10,2,7,16,4,8,9 

你先建立這種樹

  5,10,2,7,16,4,8,9 
      /  \ 
     5,10,2,7   16,4,8,9 
    / \   / \ 
    5,10  2,7  16,4  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9 

然後如果你想回答詢問說，對它們進行排序的所有

  2,4,5,7,8,9,10,16 
      /  \ 
     2,5,7,10   4,8,9,16 
    / \   / \ 
    5,10  2,7  4,16  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9 

現在（1,6,8）（索引是從0開始的）將（1,6）區間分解爲二元子區間（1）（2,3）（4,5）（6）（這裏（1）= {10}爲0，（2,3）= {2,7}爲9，（4,5）爲4則分別找到答案）= {16,4}，對於（6）= {8}爲8）並且將它們相加。

初始樹建設在（ñ日誌ñ）來完成，如果你排序對（價值指數）一次，然後就通過對有序陣列日誌n次（一次爲每個樹級別）及複印件值分配給它們各自的節點。