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

If a Binary Index Tree (Fenwick Tree) is min/max tree, can it update online?
Автор trunghieu11, 10 лет назад, По-английски

Is there any ways we can update Binary Index Tree when it's a min/max tree?

For example, I have an array:

10 4 5 6 8

tree.getMin(3) = 4; //query at index 3 the result is 4

tree.update(2, 1); //update value at index 2 from 5 to 1

tree.getMin(3) = 1; //requery at index 3 we have the new result is 1

Thanks!!

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

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

For this case there is another data structure.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This seem incorrect, I try this test:

    7 6 5

rmq.GetMax(0, 3) = 5;
rmq.SetMax(2, 11);
rmq.GetMax(0, 3) = 5; //it's must be 11
    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

similar to basic BIT:

struct FenwickTree {
	int T[N];
	
	FenwickTree() {
		for (int i=0; i<N; i++)
		T[i]=oo;
	}
	
    void update(int u, int x) {
        for (int i=u; i<N; i+=i&-i)
        T[x] = min(T[x], x);
    }
    
    int get(int u) {
    	int Min = T[u];
    	while (u-=u&-u)
    	Min = min(Min, T[u]);
    	return Min;
    }
};
→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I don't think your tree will work on the following case:

    Current array: 7 6 5
tree.getMin(3)=5;
tree.update(3,8);
tree.getMin(3)=6;

    However, on the last query your tree will return 5.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    It works only when all elements don't increase (or don't decrease if it's a max-BIT).

    → Ответить