Hello every one
Is segment tree support insertion, deletion and get kth item? and if it's possible, can you provide me with a resource or code for those functions?
I want something like this:
delete(i) ===> delete the ith item inside the segment tree.
insert(i, val) ====> insert the val in the position i inside the tree.
getKth(k) =====> get the value that is in the kth position inside the tree.
This can not be done in a segment tree. If you tried to do it in a segment tree, you will need to build the tree for each of the listed operations. You'd better use treaps or skiplists.
See this link for treaps http://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-1
Try cartesian tree (treap).
If you know exactly what elements can be inserted, you can compress the values, lets say, if the possibilities are {4, 10, 20, 330} the compressed values whould be {0, 1, 2, 3}, then build a segment tree with N leafs (N is the number of distinct elements).
I share you a code I wrote some time ago for this task: http://ideone.com/OKpT0o
check this video in arabic