import java.util.Scanner;
/**
* k 为尾部的0的个数
* C[i] = A[i - 2^k+1] + A[i - 2^k+2] + ... + A[i]
*/
public class TreeArray {
private int size;
private int arr[];
private int c[];
public TreeArray(int size) {
this.size = size;
this.arr = new int[size + 1];
this.c = new int[size + 1];
}
private int lowbit(int x) {
return x & (-x);
}
private void init(int i, int x) {
this.arr[i] = x;
add(i, x);
}
private void add(int i, int x) {
arr[i] += x;
while (i <= size) {
c[i] += x;
i += lowbit(i);
}
}
private int sum(int i) {
int s = 0;
while (i > 0) {
s += c[i];
i -= lowbit(i);
}
return s;
}
private void print() {
for (int i = 1; i <= size; ++ i) {
System.out.println(i + "--->" + arr[i]);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
System.out.println("请输入数组大小");
int n = in.nextInt();
if (n <= 0) {
break;
}
TreeArray treeArray = new TreeArray(n);
System.out.println("请输入数组元素");
for (int i = 1; i <= n; ++ i) {
int x = in.nextInt();
System.out.println(i + "--->" + x);
treeArray.init(i, x);
}
while (true) {
System.out.println("请输入指令");
String cmd = in.next();
if ("end".equals(cmd)) {
break;
} else if ("add".equals(cmd)) {
System.out.println("请输入下标");
int i = in.nextInt();
System.out.println("请输入值");
int x = in.nextInt();
treeArray.add(i, x);
treeArray.print();
} else if ("sum".equals(cmd)) {
System.out.println("请输入下标");
int i = in.nextInt();
System.out.println("1-" + i + "的和 = " + treeArray.sum(i));
} else if ("print".equals(cmd)) {
treeArray.print();
}
}
}
}
}原文：https://blog.51cto.com/tianyiya/2534270