Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

sebi420p's blog

Can 2D BIT be built in O(n^2)?
By sebi420p, 6 years ago, In English

Knowing the fact that 1D Fenwick Trees can be built in linear time, I am assuming that the 2D version can be built in quadratic time. I didn't manage to find anything about this. Can you help me with some links/ideas?

  • Vote: I like it
  • +62
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it -26 Vote: I do not like it

For every updation in linear Fenwick tree we require O(log N ) time complexity.It takes Nlog(N) for linear or 1-D. sebi420p How can we built in just O(N) .

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +37 Vote: I do not like it 
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)c[i][j]=a[i][j];
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
	if(j+(j&-j)<=n)c[i][j+(j&-j)]+=c[i][j];
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
	if(i+(i&-i)<=n)c[i+(i&-i)][j]+=c[i][j];
→ Reply
»
6 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Why is he downvoted, it's a good question.

→ Reply