segment-tree

2熱度

1回答

公司可供會議使用的會議室數量爲n個。您需要預訂特定時段的會議。寫一個算法來確定在給定的開始時間和結束時間內可用於會議的會議室的數量。提示：將選擇任何會議室與非重疊會議。我想段樹能提供這個O（logN）的，但不知道這就是每個查詢的最佳方法

0熱度

1回答

我正在嘗試構建一個用於執行RMQ的段樹。不知何故，無論我查詢什麼範圍它將返回我0. 例如，我的數組是[ 1,2,3,4,5,6,7,8,9,10 ]。 RMQ從指數3到5應該給4.但我的代碼保持輸出0 我的代碼： #include<bits/stdc++.h> using namespace std; #define ll long long ll N, st[2*100000], a

0熱度

1回答

查找範圍與體重k個項目的數量（含更新和查詢）

我試圖解決以下問題：考慮到與整型權（任意順序）項目的數組，我們可以有2個可能的操作：查詢：輸出是權重k的項，在範圍x到y的數量。更新：在一定的索引換物品的重量到v 例：鑑於數組：[1,2,3,2,5,6,7,3 ] 如果我們查詢從索引1與權重2項至3的數，則答案是2. 如果我們在索引2修改元件以具有2的權重，那麼我們再次進行相同的查詢，答案將是3. 這當然是（用點更新）段樹問題。但是，

0熱度

2回答

（python）如何更改字典中的密鑰分配？

我想要建立一個像段樹一樣的段詞典。我的意思是我想使用序列（11，22）作爲關鍵，如果輸入值像11，它應該使用相同的密鑰。如何做到這一點。例如字典是{（11,22）：35，（44,45）：12}。我想寫研究員： for i in dictionary: blad blad 如何更改詞典功能使其能夠「在」操作使用？

1熱度

3回答

周邊矩形

我想知道有效的方式來解決這個問題：鑑於給予左上角和右下角ñ矩形，請找的周邊N個矩形的聯合。我只有O(N^2)算法，它的速度太慢，所以請找到更有效的算法。可以假定座標值是正整數，並且小於100000 編輯：例如，在這種情況下，周長爲30 爲O（n^2）算法： for x=0 to maxx for i=0 to N if lowx[i] = x for j=

1熱度

1回答

爲什麼第二次深度先搜索？

最近我遇到一個問題叫Gravity Tree 我無法自己解決，所以我檢查了editorial。作者的解決方案是在頂點一次dfs並形成一個段樹，其中每個節點包含從頂點到中心的距離。然後他提到了第二個dfs（我不知道這是做什麼，我嘗試打印他的數據結構，但他們完全沒有意義，不知道他究竟想要做什麼）。他寫的語言太難以掌握了。我知道什麼是細分樹，dfs，懶散的傳播。但是我無法圍繞這個解決方案。不知道解決方案

2熱度

2回答

線段樹空間需求

我已發現，如本文on HackerEarth該線段樹能夠通過使用陣列來實現在說明了定位在陣列的索引Ñ是在索引2n個和2N + 1的節點的子元素。此外，它指出，對於存儲在我的段樹ñ元素，我需要2N + 1節點。然而，最近當我解決了與分段樹相關的一些問題時，有時我的代碼給出了運行時錯誤，當我將存儲分段樹的數組大小更改爲4 x（要存儲在分段樹）。我如何確定段樹實際上需要n個元素的4n大小的數組。

0熱度

1回答

更新分段樹中的一個項目

我正在解決的問題的一部分涉及獲取數組（RMQ）的範圍中的最小值，所以我實現了一個分段樹並且迄今爲止工作正常。然後，我想更新原始數組中的一個項目（沒有多個更新），並在分段樹中進行更新。我到目前爲止所做的是從上到下遍歷分段樹，直到到達樹葉，但似乎有一些錯誤。這裏是代碼的更新部分，那裏有什麼錯誤？ P.S. n是不是2的倍數（我不知道這是否會影響解決方案） public void update(int

-3熱度

1回答

記性不好的alloc錯誤 - 段樹

我想創建一個分段樹，這裏是我的樹的節點結構： struct Node{ int x1, x2; // x coordinates int y1, y2; // y coordinates Node * v1; Node * v2; Node * v3; Node * v4; bool oBo; //check if 1 by

4熱度

1回答

線段樹查詢爲最大數

我已經給定的n整數的數組A，並且在X D爲每個查詢我必須找到最大元件在子陣列[Ax , A(x-D),A(x-2D)..] 例如形式Q查詢： A = [1,2,3,4,5,6,17,8] we have query 7 2 Sub Array [17,5,3,1] Ans=17 我們怎樣才能用的時間複雜度比O(Q*N)因爲沒有索引更新更好的解決這個問題，能不能用一些技術我不離線解決t認爲