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

Can 2D BIT be built in O(n^2)?
Автор sebi420p, 4 года назад, По-английски

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?

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

»
4 года назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

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) .

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится 
	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];
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

→ Ответить