Блог пользователя I_love_Jiang

Ask something about Fenwick tree !!!
Автор I_love_Jiang, история, 8 лет назад, По-английски

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 !!

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  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.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

→ Ответить