×

# Segment Tree

 0 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 187●2●13 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)

 1 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! answered 15 Apr '17, 18:00 4★glebodin 111●4 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) you'are welcome! And of course>x!It's my fault!)))) (16 Apr '17, 00:01) glebodin4★
 0 For those who are still interested in solving this problem can follow this link http://codeforces.com/blog/entry/51582 answered 15 Apr '17, 21:57 187●2●13 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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