A weird segment tree problem

Revision en2, by rakkoon69, 2023-10-03 19:41:46

Given an array of n integers equal to zero. There are 3 type of queries:

  1. Increase all elements from l to r by 1
  2. Decrease all elements from l to r by 1
  3. Count the number of zeros from l to r

Is there an efficient way to solve this problem in O(N log N), O(N sqrt(N)) or at least O(N log2 N)? Thank you in advance!

I've found a O(N log N) solution which I've implemented in 258E - Little Elephant and Tree, my submission: 226468052 (The STree namespace)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English rakkoon69 2023-10-03 19:41:46 138 Tiny change: '26468052] ' -> '26468052] (The STree namespace)'
en1 English rakkoon69 2022-07-16 13:13:54 357 Initial revision (published)