trunghieu11's blog

If a Binary Index Tree (Fenwick Tree) is min/max tree, can it update online?
By trunghieu11, 10 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

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

For this case there is another data structure.

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

    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
    → Reply
»
10 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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;
    }
};
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    → Reply