二次元累積和

rui2D R(v) でvの二次元累積和を作る

R.query(a,b,c,d)で

(a,b)(   )(   )
(   )(   )(   )
(   )(   )(c,d)  

の区間の累積を取る

class rui2D{
    public : 
    vector<vector<long long>> v;
    rui2D(vector<vector<long long>>& a){
        v = a;
        long long h = v.size();
        long long w = v[0].size();
        for(long long i = 0;i < h;i++){
            for(long long j = 1;j < w;j++){
                v[i][j] += v[i][j-1];
            }
        }
        for(long long j = 0;j < w;j++){
            for(long long i = 1;i < h;i++){
                v[i][j] += v[i-1][j];
            }
        }
    }
    long long query(long long a,long long b,long long c,long long d){
        long long ans = v[c][d];
        if(a!=0)ans -= v[a-1][d];
        if(b!=0)ans -= v[c][b-1];
        if(a!=0 && b != 0)ans += v[a-1][b-1];
        return ans;
    }
};