How to solve Gru's Study: Hackerrank problem

help
,
1

Can someone tell me a good editorial or any best approach to solve this hackerrank problem?

2

This problem is just asking you to perform range updates and range queries in two dimensions, where every range is a rectangle. There are many ways to solve this, but as far as I know, the easiest (to implement) is using a 2D BIT/Fenwick tree. Read this if you don’t already know what a BIT is :

http://theoryofprogramming.com/2014/12/24/binary-indexed-tree-or-fenwick-tree/

And then, read this to understand how the 2D version works :

1 Like
3

You can find the editorial here:

https://drive.google.com/file/d/17I8-PirwL2dVFF-3KdTfZVsDnS4HSB8e/view

4

I knew about this and have already seen the editorial, but still I’m having a difficulty in understanding the approach that they used in editorial and how they are performing sub-matrix update in \log n time ?