killua123's blog

By killua123, history, 10 months ago, In English

https://mirror.codeforces.com/contest/1928/submission/246087824

I am new to range query data structures so i am treating fenwick tree as a black box. I know the working of fenwick but not able to code a 2d one.

I asked chatgpt for help it is giving wrong code I want it similar to this template so if anyone can help me with it.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Because the problem allows for $$$O(N^2)$$$ memory, just put a Fenwick tree in every single node of a Fenwick tree to make it 2-dimensional.

Untested code

This will allow for point update and range query in $$$O(log^2\,N)$$$ time for both.