这个题是比较基础的树状数组的题目了,但是鉴于还是小白,而且为了一些跟我一样的学java的小白,还是把对这个题目的理解写的透一点吧。
题目的大意就是让你求一个S*S的表格中一些格子里所包含的手机个数的和。
输入:
输入0的时候,后面的数S就是所建立表格的大小S*S【用二维数组表示】;输入1的时候,在(X,Y)格中加入A个手机;输入2的时候,计算从(L,B)到(R,T)的所有格子的手机的总数,并且输出;输入3的时候,结束程序。
AC代码如下【小白必然代码不优雅】
import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int s=scan.nextInt(); int C[][]=new int [s+1][s+1]; while(n!=3) { if(n==1) { int X=scan.nextInt()+1; int Y=scan.nextInt()+1; int A=scan.nextInt(); Change(Y,X,A,C); } if(n==2) { int L=scan.nextInt()+1; int B=scan.nextInt()+1; int R=scan.nextInt()+1; int T=scan.nextInt()+1; int sum=Sum(T,R,C)-Sum(T,L-1,C)-Sum(B-1,R,C)+Sum(B-1,L-1,C); System.out.println(sum); } n=scan.nextInt(); } } public static int lowbit(int l) { return l&(-l); } public static int Sum(int Y,int X,int[][] C) { int sum=0; for(int y=Y;y>0;y-=lowbit(y)) for(int x=X;x>0;x-=lowbit(x)) sum+=C[y][x]; return sum; } public static void Change(int Y,int X,int A,int[][] C) { int length=C.length; for(int y=Y;y<length;y+=lowbit(y)) for(int x=X;x<length;x+=lowbit(x)) C[y][x]+=A; } }