Hey guys, can you please give me some sources with easy BIT 2D implementation? I would be grateful also for some problems using this from easy to hard. Thanks in advance!

# | User | Rating |
---|---|---|

1 | tourist | 3539 |

2 | V--o_o--V | 3338 |

3 | Um_nik | 3307 |

4 | Petr | 3297 |

5 | ecnerwala | 3282 |

6 | LHiC | 3266 |

7 | wxhtxdy | 3264 |

8 | Radewoosh | 3257 |

9 | Vn_nV | 3182 |

10 | dotorya | 3178 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 207 |

2 | Errichto | 177 |

3 | neal | 159 |

4 | Ashishgup | 158 |

5 | PikMike | 157 |

6 | majk | 156 |

6 | Petr | 156 |

8 | rng_58 | 155 |

9 | Um_nik | 154 |

10 | 300iq | 153 |

Hey guys, can you please give me some sources with easy BIT 2D implementation? I would be grateful also for some problems using this from easy to hard. Thanks in advance!

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/24/2019 04:39:34 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Topcoder has a great tutorial: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

I know only one problem that can be solved using 2D BIT: http://codeforces.com/problemset/problem/869/E

Thanks!

I know another one problem that can be solved using 3D BIT (100246B - B), but its statement only available in russian. But i can

tryto translate it.You are given a cube (coordinates of points in a cube is 0-indexed) with a side

n(1 ≤n≤ 128) and 2 types of queries. Each query starts with its type (1 or 2). Type 1 is followed by 4 integersx,y,z,k(x,y,z— coordinates,k( - 2·10^{4}≤k≤ 2·10^{4}) — the number of appeared/lost stars in this point (i don't know that i wrote it understandable) (i.e. that query means such operation:cube[x][y][z] + =k). Type 2 query is followed by 6 integersx1,y1,z1,x2,y2,z2 — coordinates of subcube, you have to count number of stars in it (i.e.forxin[x1;x2]:foryin[y1;y2]:forzin[z1;z2]:res+ =cube[x][y][z]).So, in conclusion, no matter how many dimensions we have, always we can apply BIT (if the statement ask for it)

I think for higher dimensions, it is best to think of it as the number of points enclosed in the n-dimensional structure.... Like in 1D the BIT is used to calculate the prefix sum ... it is in a way looking back from current point up until origin and calculating some type of summation, extend this to n-dimensions and you will agree with my first statement.

I was reading 2D BIT, gfg implementation https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/

Please help me with some doubts, In the updateBit and getSum function inner "y" loop is not initialized again. Is it a mistake or is it meant to be that way?

If it is meant to be that way can you explain how is it working and what is the need of outer loop as the same work can be done with the help of an "if" statement.

Thanks in advance..

That's probably a mistake, since I've tried it and it got WA. I always use 2D fenwick initializing the nested variable.

here is another problem that can be solved using 2D BIT: https://codeforces.com/contest/1093/problem/E

Hello, i use the implementation of BIT 2D present in this notebook. I hope helps! :) Sorry the codes are in english, but the comments are in portuguese.

https://github.com/Gabriel123Duarte/maratona-final/blob/master/Notebook/100%5Eo.pdf