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

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

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
  • Проголосовать: не нравится

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

For this case there is another data structure.

→ Ответить
»
12 лет назад, скрыть # |
 
Проголосовать: нравится -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;
    }
};
→ Ответить