sebi420p's blog

Can 2D BIT be built in O(n^2)?
By sebi420p, 4 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

»
4 years ago, # |
  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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, we can build a bit in O(n). Every index in a bit indicates the sum of the range [i — lowbit(i), i]. So, if you build a prefix sum array beforehand, you can use it to build the bit in O(n).

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can check this link

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

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

→ Reply