Segment Tree

general
,
1

Hi, i was wondering how would we carry out these operation on an array using segment tree.

Formal statement of the problem.

Given an array if N positive integers, and Q queries perform these operations.

1 L R X. Decrease every element in the range [L…R] by by value X

2 L R. Return how many element in the range[L…R] are strictly greater than 0

N, Q <= 10^5

0 <= X

What information would i hsve to store in each node to get answer ?

2

@mathecodician. Which ongoing contest, this question is related to ?

For me this is from one of the practice problem, so if it really is from any current contest, do lock this question.

Do comment the link of the question, after the contest obviously.

3

It is a easy problem, once you understand segment tree, it won’t be tough to implement. Go through these tutorials

  1. https://youtu.be/Oq2E2yGadnU
  2. videos of tushar roy on segment tree (google this)
  3. https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
  4. http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/

Once you understand the basic you’ll do it, at least put a day of effort and still if you cannot, request for code.

1 Like
4

Okay,let’s save sorted subarray of this vertex:
then

  1. update: let’s save in vertex that all elements -x
  2. let’s do bin.search to the amount of numbers>=x
    That’s all:
    Memory : o(nlogn), because one number will be in log(n) vertex;
    Time : o(log^2n), bin.search+segment_tree;
    If you have any questions, ask me!
    Sorry for my English!
1 Like
5

you need it coded so u downvoted? @ashwanigautam

6

I think that guy is indeed psycho! We guys are helping out but he down voted without any specific reason

1 Like
7

exactly, it would have been helpful to him, if someone has coded it for him, according to his theory :frowning:

8

No, i did not want it to be coded, indeed if you would have read the question at least once you would have realised what i wanted.

I down-voted because i didn’t asked for links to tutorial and blog. Read the question again if you want to.

I knew about segment tree and lazy propagation, which i repeated to you @bansal1232.

If it is an “easy” problem then one of you could have given some hints to a “psycho”(you guys are calling me names just because i down-voted? are you guys sure about your education).

In short, I down-voted because your answers DO NOT address the question.

3 Likes
9

Hi, your solution is almost correct, it just needs some fixing here and there.

here is the link to some discussion, http://codeforces.com/blog/entry/51582#comments

your approach is similar to one explained by rachitjain. Thanks for answering.

10

For those who are still interested in solving this problem can follow this link

http://codeforces.com/blog/entry/51582

11

you’are welcome! And of course>x!It’s my fault!))))