ფენვიკი

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;
int n,a[1025][1025],b[2001][2001],m,l,r,s1,s,x,y,x0,yy,t,num;
char st[5];
void update (int x, int y, int q){
    q=q-a[x][y];
    a[x][y]+=q;
    for (int i = x; i < n; i = (i | (i+1)))
        for (int j = y; j < n; j = (j | (j+1)))
            b[i][j] += q;
}
int sum (int x, int y){
        if (x<0 || y<0 ) return 0;
    int s = 0;
    for (int i = x; i >= 0; i = (i & (i+1)) - 1)
        for (int j = y; j >= 0; j = (j & (j+1)) - 1)
            s += b[i][j];
    return s;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&t);
    for (int k=1;k<=t;k++){
      for (int i=0;i<=n;i++)
      for (int j=0;j<=n;j++){
        a[i][j]=0;
        b[i][j]=0;
      }
      scanf("%d",&n);
      while (1){
        scanf("%s",&st);
        if (st[2]=='D'){puts(""); break;}
        if (st[2]=='T') {
                scanf("%d",&x);
               scanf("%d",&y);
               scanf("%d",&num);
            update(x,y,num);
        }
        if (st[2]=='M'){
                scanf("%d",&x0);
               scanf("%d",&yy);
                scanf("%d",&x);
               scanf("%d",&y);
          int ans=sum(x,y)-sum(x,yy-1)-sum(x0-1,y)+sum(x0-1,yy-1);
          printf("%d\n",ans);
        }
      }
    }
    return 0;
}