Mhammad1's blog

Segment Tree (Insert and Delete)?

By Mhammad1, history, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Try cartesian tree (treap).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

check this video in arabic

→ Reply