I_love_Jiang's blog

Ask something about Fenwick tree !!!
By I_love_Jiang, history, 7 years ago, In English

Hi everybody !

I've learn to use Fenwick Tree for a long time but recently I perceive I didn't use it optimally.

So I have some question about Fenwick Tree, I need your help :

1, Can we use Fenwick Tree for min-max query for an inteval array;

2, Can we use it as a Dynamic Fenwick Tree with number of nodes not exeed 1e9 and how to.

3, Can we one Fenwick Tree for two usages: sum and min or sum and max.

They maybe fool questions, please help me if you can !!

Sorry because of my poor English !!

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

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

For 1, consult this paper : http://www.ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

for second, yes, using map instead of normal array, log(n) time slower of course

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

    Can you explain a bit more? How will you use map to get dynamic BIT?

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  1. I know that Fenwick tree can be used for min-max queries but it is harder to implement than segment trees (I haven't seen anybody using it yet). There is a special case when you can use same principle as for cumulative sum. You can use similar implementation as if you are interested in min-max query of first x elements (left side of interval is always 1).
  2. You can read more about it here: http://stackoverflow.com/questions/21995930/dynamic-i-e-variable-size-fenwick-tree
  3. I guess the story is same as with segment tree. Every node is struct that contains more values (I must admit that I have never implemented it).

I hope this helps.

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

I don't see why this post deserve 8 downvotes. OP's just trying to learn, why downvote?

→ Reply