Segment Tree Query

Revision en1, by i_love_emilia_clarke, 2017-04-15 13:00:34

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 <= 10000

Initial values of array can be as large as 1 000 000 000 What information would i have to store in each node ?

Tags segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English i_love_emilia_clarke 2017-04-15 13:00:34 530 Initial revision (published)