You are not logged in. Please login at www.codechef.com to post your questions!

×

Segment Tree

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 ?

asked 15 Apr '17, 10:47

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

@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.

(15 Apr '17, 11:50) ashwanigautam3★

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!

link

answered 15 Apr '17, 18:00

glebodin's gravatar image

4★glebodin
1114
accept rate: 0%

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.

(15 Apr '17, 21:56) ashwanigautam3★

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

(16 Apr '17, 00:01) glebodin4★

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.

link

answered 15 Apr '17, 12:21

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%

edited 15 Apr '17, 12:22

you need it coded so u downvoted? @ashwanigautam

(15 Apr '17, 18:55) neilit19923★
1

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

(15 Apr '17, 19:12) bansal12325★

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

(15 Apr '17, 19:32) neilit19923★
3

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.

(15 Apr '17, 21:51) ashwanigautam3★

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

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

link

answered 15 Apr '17, 21:57

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,726
×164

question asked: 15 Apr '17, 10:47

question was seen: 743 times

last updated: 16 Apr '17, 00:03