子段求和

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1081

给出一个长度为N的数组，进行Q次查询，查询从第i个元素开始长度为l的子段所有元素之和。
例如，1 3 7 9 -1，查询第2个元素开始长度为3的子段和，1 {3 7 9} -1。3 + 7 + 9 = 19，输出19。

Input

第1行：一个数N，N为数组的长度(2 <= N <= 50000)。
第2 至 N + 1行：数组的N个元素。(-10^9 <= N[i] <= 10^9)
第N + 2行：1个数Q，Q为查询的数量。
第N + 3 至 N + Q + 2行：每行2个数，i，l（1 <= i <= N，i + l <= N)

Output

共Q行，对应Q次查询的计算结果。

Input示例

5
1
3
7
9
-1
4
1 2
2 2
3 2
1 5

Output示例

4
10
16
19

分析：

树状数组模版题

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int N = (int) in.nval;
		BinaryIndexedTree tree = new BinaryIndexedTree(N);
		for (int i = 1; i <= N + 1; i++) {
			in.nextToken();
			int a = (int) in.nval;
			tree.put(i, a);
		}
		int Q = (int) in.nval;
		for (int i = 0; i < Q; i++) {
			in.nextToken();
			int k = (int) in.nval;
			in.nextToken();
			int l = (int) in.nval;
			out.println(tree.sum(k + l - 1) - tree.sum(k - 1));
		}
		out.flush();
	}

	static class BinaryIndexedTree {
		int length;
		long[] tree;

		BinaryIndexedTree(int length) {
			this.length = length;
			tree = new long[length + 1];
		}

		void put(int index, int value) {
			while (index <= length) {
				tree[index] += value;
				index += lowBit(index);
			}
		}

		static int lowBit(int k) {
			return k & -k;
		}

		long sum(int index) {
			long sum = 0;
			while (index > 0) {
				sum += tree[index];
				index -= lowBit(index);
			}
			return sum;
		}
	}
}