har_vi's blog

SPOJ GSS4 (BIT+UFDS) HELP WITH IDEA
By har_vi, history, 8 years ago, In English

Range updates or range set with BIT/fenwick tree

SPOJ/GSS4

  1. How should I do range updates with BIT using Union Find Data Structure?what would be expected complexity?
  2. In this case max updates can be 7.N*logN but what if we set number in range to random number which don't have such relation with the input.Would it still possible to do it with BIT/fenwick tree or there's any other approach to set elements in range to a given.

Thanks!

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used intelligent brute force, just skip the one's in the array is our objective.
So I keep Left and Right arrays which give me the nearest index with number > 1 .
The sum query is trivial , I used fenwick to support this type of query.

Code

→ Reply