Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Policy Based Persistent BIT

Revision en2, by hahavodox, 2017-10-08 01:00:08

Recently I came across a technique similar to Policy based DS, a Policy Based Persistent BIT. To basic idea is to keep the BIT balanced by HLD. Naive algo is O(n^2). But you have to optimize using bitset to make it O(nlog n). You can perform dynamic range update range query and orthogonal range minimum IDA* search easily in O(Nlog N).

Example:http://codeforces.com/contest/869/problem/E

This can be solved with this trick easily combining this with Baby Step Giant Sweep line along with persistent KSAT.

Tags hld, bit, persistence, ds, monopoly, koto kichu pari, safety pin, bitset

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English hahavodox 2018-12-29 12:30:00 4
en3 English hahavodox 2018-12-18 21:35:18 0 (published)
en2 English hahavodox 2017-10-08 01:00:08 16 (saved to drafts)
en1 English hahavodox 2017-10-08 00:47:02 543 Initial revision (published)