Prelude: this post assumes the reader already know the concepts behind Binary Indexed Trees, as I will not be explaining them here.
Let's talk about 2-dimensional Binary Indexed Trees. The implementation of 2D BIT usually goes as follows:
- Implement a standard, 1D BIT, with update and query functions;
- Implement 2D update and query; these look exactly the same as the 1D case, except basic operations are replaced by calls to the 1D versions of these operations.
This is OK and works well for most cases. However, there are some issues with this implementation:
- 2D methods are usually implemented (for coding speed reasons), by copy-pasting the 1D code and changing the operations. Copy-pasting is always risky, since it's so easy to miss a change you're supposed to make.
- It doesn't feel "clean". There's duplicate code in there that makes the source harder to read (and maybe debug). Also, if you've messed up something in one of the dimensions (for example, you wrote
<instead of<=), chances are you've also missed it on the other one; and you have to remember to modify it in both places. - It doesn't scale well. Issues #1 and #2 are heavily amplified when more than 2 dimensions are concerned. In fact, it was a problem which required 3D BIT that motivated me to write this post.
