Mhammad1's blog

Segment Tree (Insert and Delete)?

By Mhammad1, history, 10 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?
»
10 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
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Try cartesian tree (treap).

→ Reply
»
10 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
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

check this video in arabic

→ Reply