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

Автор -synx-, 7 лет назад, По-английски

This Blog shows how we can adapt segment tree update and query functions for 1D case to code the 2D query and update. My question is can we code iterative build function for the 2D Segment Tree by adapting the 1D build function:

void build(){
	for(int i=n-1;i>0;--i) 
		t[i] = t[i<<1] | t[i<<1|1];
}

Note: Although we can use the update function to build the 2D segment tree, but its complexity would be O(nmlog(n)log(m)), however the iterative 2D build function would ensure O(nm).

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