PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 主席樹？

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/02/07 23:47)推噓0(0推 0噓 2→)

留言2則, 1人參與討論串4/4 (看更多)

我研究了一下，如果元素有 n 個，查詢有 m 個，當 m 至少為 n^0.5，莫隊算法那空間複雜度應該會是 O((n+m) * n^0.5 * (狀態轉移cost) + 排序) 空間是 O(m+狀態表示)。所以我猜主要的優勢是在好實作和省空間吧。我嘗試了幾個題目（假設m = O(n)） 1. Range inversion counting: 求區間內的逆序對 2. Range sum of distinct elements: 區間內相異元素之和 3. Range second frequency moment: 求區間內元素出現次數的平方和 4. Range mode query: 求區間內的眾數 1 的 offline 查詢為 O(n^0.5 lg n) online 查詢為 O(n^0.5) 空間 O(n^1.5) 或查詢為 O(n^0.5 lg n) 空間 O(n) 2, 3, 4 的 offline 查詢為 O(n^0.5) 4 的 online 查詢為 O(n^0.5) 空間 O(n) 2, 3 的 online 查詢為 O(n^0.5) 空間 O(n^1.5) 或查詢為 O(n^0.5 lg n) 空間 O(n) 不知道能不能做成查詢為 O(n^0.5) 空間 O(n) 至於動態的話，就把 block 大小調小一點就可以了。好像還有看到題目是 range distinct elements，找區間相異數字的個數，這應該是O(lg n)可解的。還有一些相關的問題，像是區間 majority，區間 minority，區間前 k 大 (sorted/unsorted)，或是區間出現最多次的 k 個元素。 -- 這技巧蠻有趣的，不知道還有沒有其他神奇的技巧呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1423324040.A.C3E.html ※ 編輯: FRAXIS (129.170.195.149), 02/09/2015 23:24:59