Binary Indexed Tree 2D (BIT-2D)

#include<bits/stdc++.h>
#define ll long long

// Usage:
//      BIT2D_Sum bit(n, m);
//      bit.clear_for(n, m);
//      bit.update_point(x, y, v);
//      summ = bit.query(x1, y1, x2, y2);
template <typename T> 
struct BIT2D_Sum 
{
    int n, m;
    T **BIT;
    
    BIT2D_Sum(int n_, int m_) {
        
        n = n_; m = m_;
        
        BIT = new T*[n+1];
        for (int i = 0; i <= n; ++i) {
            BIT[i] = new T[m+1];
            fill(BIT[i], BIT[i] + m + 1, 0);
        }
    }
    
    void clear_for(int n_, int m_) {
        
        n = n_; m = m_;
        
        for (int i = 0; i <= n; ++i) {
            fill(BIT[i], BIT[i] + m + 1, 0);
        }
    }
    
    void update_point(int posx, int posy, T v) {
        
        for (int x = posx; x <= n; x += x&(-x))
            for (int y = posy; y <= m; y += y&(-y))
                BIT[x][y] += v;
    }
    
    T query(int posx, int posy) {
        
        T res = 0;
        
        for (int x = posx; x > 0; x -= x&(-x))
            for (int y = posy; y > 0; y-= y&(-y))
                res += BIT[x][y];
        
        return res;
    }
    
    T query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x2, y1-1) - query(x1-1, y2) + query(x1-1, y1-1);
    }
    
};