jaswanthi's blog

Fenwick Tree, N unique elements which may have values greater than N
By jaswanthi, history, 9 years ago, In English

Given an Array N unique elements ,and some elements may contain values greater than N.

For ex: 1, 8, 2147483647

To work on Fenwick Tree, we need to adjust that to a 1 — N range. Is there a way to do this ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Sort the values, then map each value to its position in the sorted array.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can write Fenwick Tree on map( O(logMAX*logMAX) ).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

use co-ordinate compression.

→ Reply