现在的位置: 首页 > 综合 > 正文

POJ 1195 树状数组 JAVA版

2017年11月23日 ⁄ 综合 ⁄ 共 1046字 ⁄ 字号 评论关闭

这个题是比较基础的树状数组的题目了,但是鉴于还是小白,而且为了一些跟我一样的学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;
	   }
	}

 

 

【上篇】
【下篇】

抱歉!评论已关闭.