Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Policy Based Persistent BIT
Difference between en3 and en4, changed 4 character(s)
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.↵

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)