hdu1166 敌兵布阵 线段树求和

HDU1166：敌兵布阵
线段树问题：
涉及：线段树创建、增减、查询

总结：

• 借助数据结构中的线段树结构来存储数据元素，Creat创建线段树，使用Add进行增减，Query进行查询。
• tree.l代表左孩子，tree.r代表右孩子，tree.sum代表区间[l,r]的总人数，head代表第几个结点，默认根节点为1。
• 建树的时候head为1，遵循结点左下角为head*2，右下角为head*2+1。
• 线段树的结点要开到4*N。
• 在Creat函数中无法输入并传值给main函数，可以借助静态一维数组。

import java.util.Scanner;

class Node {// 结点类
	int l, r;
	int sum;

	Node(int l, int r, int sum) {
		this.l = l;
		this.r = r;
		this.sum = sum;
	}
}

public class Main {
	static final int N = (int) (5e4 + 10);// 50000个整数
	static int[] p = new int[50001];// 存储结点位置

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Node[] tree = new Node[N * 4];// 定义根节点
		for (int i = 0; i < tree.length; i++) {// 根节点初始化
			tree[i] = new Node(0, 0, 0);
		}
		int T = in.nextInt();
		for (int i = 1; i <= T; i++) {
			int N = in.nextInt();
			for (int j = 1; j <= N; j++) {
				p[j] = in.nextInt();
			}
			Creat(tree, 1, 1, N);
			System.out.println("Case " + i + ":");
			while (in.hasNext()) {
				String s = in.next();
				if (s.compareTo("End") == 0)
					break;
				int a = in.nextInt();
				int b = in.nextInt();
				if (s.compareTo("Query") == 0)
					System.out.println(Query(tree, 1, a, b));
				else if (s.compareTo("Add") == 0)
					Add(tree, 1, a, b);
				else if (s.compareTo("Sub") == 0)
					Add(tree, 1, a, -b);
			}
		}
	}

	static void Creat(Node[] tree, int head, int L, int R) {// 创建线段树
		tree[head].l = L;
		tree[head].r = R;
		if (tree[head].l == tree[head].r) {// 如果到达低端
			tree[head].sum = p[L];
			return;
		}
		int mid = (tree[head].l + tree[head].r) >> 1;
		Creat(tree, head << 1, L, mid);
		Creat(tree, head << 1 | 1, mid + 1, R);
		tree[head].sum = tree[head << 1].sum + tree[head << 1 | 1].sum;
		return;
	}

	static int Query(Node[] tree, int head, int L, int R) {// 查询语句
		int ans = 0;
		if (tree[head].l == L && tree[head].r == R)// 查询到父结点
			return tree[head].sum;
		int mid = (tree[head].l + tree[head].r) >> 1;
		if (mid < L)
			ans += Query(tree, head << 1 | 1, L, R);
		else if (mid >= R)
			ans += Query(tree, head << 1, L, R);
		else {
			ans += Query(tree, head << 1, L, mid);
			ans += Query(tree, head << 1 | 1, mid + 1, R);
		}
		return ans;
	}

	static void Add(Node[] tree, int head, int x, int num) {// 添加函数
		if (tree[head].l == x && tree[head].r == x) {// 找到了
			tree[head].sum += num;
			return;
		}
		if (tree[head].l == tree[head].r)
			return;
		int mid = (tree[head].l + tree[head].r) >> 1;
		if (x <= mid)// 加左边
			Add(tree, head << 1, x, num);
		else
			// 加右边
			Add(tree, head << 1 | 1, x, num);
		tree[head].sum = tree[head << 1].sum + tree[head << 1 | 1].sum;// 加父结点
		return;
	}
}