How can I delete a node from a segment tree?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP



How can I delete a node from a segment tree?



I'm trying to solve a problem in which I am given a list of numbers and a set of operations. The operations are:


1-print the minimum element of the list and then delete it
2-"p" and "x" are given and the element in position "p" will be given the value "x"



So I thought about using a segment tree, considering that it's easy to determine the minimum of a list and to change an element's value using such a data structure(with the "update" and "query" functions). The problem I encountered was at the deletion of the minimum part. I don't know how could I delete a node from a segment tree so instead I changed the minimum element's value to infinity, sent my code on the website and it didn't get maximum points. If someone can tell what I'm doing wrong and how to solve it I would be really grateful.





That doesn't look like a job for a segment tree.
– m69
Aug 13 at 1:28





@Bogdan Vlad, can you post the whole question, your post isn't clear
– zenwraight
Aug 13 at 3:49





Why use a tree at all? Just use an array
– Mitchel Paulin
Aug 13 at 15:01





@zenwraight The questions is not in english so I will try my best to translate it: You are given a list of numbers on which two types of operations can be done: updating an item (changing its value) and determining, and then deleting, of the minimum element. If the minimum value occurs multiple times in the list, its first occurrence is deleted. It is believed that the elements on the right of the removed element move a position to the left(covers the gap left). I tought that I should solve it with segment trees because I found this problem in the "segment tree" chapter of the website.
– Bogdan Vlad
Aug 13 at 15:51





@Mitchel0022 I need to solve the problem in logarithmic time, which is not possible (as far as I know) using arrays. Sure, you can find the minimum element in logarithmic time using binary search, but then to delete it you would need to move all the elements to the right of the minimum one position to the left to cover the gap and that would take O(n).
– Bogdan Vlad
Aug 13 at 15:54










By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

-

Popular posts from this blog

Firebase Auth - with Email and Password - Check user already registered

Image
Clash Royale CLAN TAG #URR8PPP Firebase Auth - with Email and Password - Check user already registered I want to check when a user attempts to signup with createUserWithEmailAndPassword() in Firebase user Authentication method, this user is already registered with my app. createUserWithEmailAndPassword() 8 Answers 8 To detect whether a user with that email address already exists, you can detect when the call to createUserWithEmailAndPassword () fails with auth/email-already-in-use . I see that @Srinivasan just posted an answer for this. createUserWithEmailAndPassword () auth/email-already-in-use Alternatively, you can detect that an email address is already used by calling fetchSignInMethodsForEmail() (previous called fetchProvidersForEmail() ). fetchSignInMethodsForEmail() fetchProvidersForEmail() When the user trying to create an user with same email address, the task response will be "Response: The email address is already in use by another account." mFirebas
Read more

Dynamically update html content plain JS

Image
Clash Royale CLAN TAG #URR8PPP Dynamically update html content plain JS So I have a script bound in my index.html, which literally has to fetch an array of jsons from an api, then dynamically update my page when get response. But as a result I'm getting an as the only update of my page. here is my script fetch(url) .then((resp) => resp.json()) .then((resp) => resp.results.forEach(item => fetch(item.url) .then((response)=> response.json()) .then((response) => pokeArr.push(response)) .catch(console.log) ) ).catch(console.log) const filler = () => if(!pokeArr) return 0 pokeArr.map((i,j)=> return `<tr>$i.name</tr>` ) const pokeindex = () => document.getElementById('a').appendChild(document.createElement(filler())) pokeindex() When I'm consoling it, I can see in the console all the responses I get, so I'm at least doing the fetching part right. What's parberakan ? What's pokeArr ? – T.J. Crowder Aug 8 at 12
Read more

How to determine optimal route across keyboard

Image
Clash Royale CLAN TAG #URR8PPP How to determine optimal route across keyboard I'm trying to automate the typing process in a video game. Players are given an on-screen QWERTY keyboard layout that they can navigate with the control stick (up, down, left, right) in order to select a letter to type. I was wondering if there was a module for Python (or some other resource I could explore) that would help my program find a path across the keyboard as it types each letter in a given message. In other words, if the first letter typed was "A" and the next letter was "B", the module would know that the program should move 1 space down on the keyboard and 4 spaces to the right. Currently, I have the program resetting to the "G" key after each letter is typed (allowing me to use fixed-directions as the program parses each character in the desired message). As you can imagine, this is quite inefficient and defeats the purpose of automating the typing in the fir
Read more