题目：南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。 思路：可以通过暴力的方法来解决但是算法的复杂度就很高了，也可以采取树状数组来解决，这样可以改善对sum值的修改时间。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); int m=input.nextInt(); int arr[]=new int[n+1]; for (int i = 1; i <=n; i++) { int t=input.nextInt(); add(n,i, t, arr); } String str; int index,temp; while (m-->0) { str=input.next(); index=input.nextInt(); temp=input.nextInt(); if (str.equals("QUERY")) { System.out.println(sum(temp, arr)-sum(index-1, arr)); }else if (str.equals("ADD")) { add(n, index, temp, arr); } } // TODO Auto-generated method stub } public static int lowbit(int x){ return x&(-x); } public static int sum(int y,int arr[]){ int sum=0; while (y>0) { sum+=arr[y]; y-=lowbit(y); } return sum; } public static void add(int n,int a,int b,int arr[]){ for (int i = a; i <=n; i+=lowbit(i)) { arr[i]+=b; a+=lowbit(b); } } }