一问题描述

A 国在海岸线沿直线部署了 N 个工兵营地，C 国通过先进的监测手段，对 A 国的每个工兵营里的人数都掌握的一清二楚，每个工兵营的人数都可能发生变动，可能增加或减少若干人数。

二输入和输出

1 输入

第 1 行包含一个整数，T 表示有 T 组数据。每组数据的第 1 行都包含一个正整数，N 表示 N 个工兵营地。接下来的 N 个正数数，第 i 个正数数 ai 代表第 i 个工兵营地开始时有 ai 个人，在接下来的每行都有 1 条命令，每组数据最多有40000 条命令。命令有四种形式。

Add i j：第 i 个营地增加 j 个人

Sub i j：第 i 个营地减少 j 个人

Query i j：查询第 i ~ j 个营地的总人数

End：退出

2 输出

对第 i 组数据，首先单行输出 Case i，然后对每个 Query 都单行输出查询区间的总人数。

三输入和输出样例

1 输入样例

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

2 输出样例

Case 1:
6
33
59

四分析和设计

1 分析

本问题包含点更新和区间查询，可以采用树状数组或者线段树解决。

2 算法设计

a 创建线段树存储区间和。

b 点更新，查询到该点后进行点更新，返回时更新区间和。

c 区间查询，首先查找该区间，然后返回区间和值。

五代码

package com.platform.modules.alg.alglib.hdu1166;public class Hdu1166 {public String output = "";private final int maxn = 55555;private int a[] = new int[maxn];private int sum[] = new int[maxn << 2];// 更新和值void PushUP(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}// 构建线段树void build(int l, int r, int rt) {if (l == r) {sum[rt] = a[l];return;}int m = (l + r) >> 1;build(l, m, rt << 1);build(m + 1, r, rt << 1 | 1);PushUP(rt);}// 单点更新void update(int p, int add, int l, int r, int rt) {if (l == r) {sum[rt] += add;return;}int m = (l + r) >> 1;if (p <= m) update(p, add, l, m, rt << 1);else update(p, add, m + 1, r, rt << 1 | 1);PushUP(rt);}// 区间查询int query(int L, int R, int l, int r, int rt) {if (L == l && r == R)//判断条件为相等return sum[rt];int m = (l + r) >> 1;if (R <= m)return query(L, R, l, m, rt << 1);else if (L > m)return query(L, R, m + 1, r, rt << 1 | 1);else return query(L, m, l, m, rt << 1) + query(m + 1, R, m + 1, r, rt << 1 | 1);}public String cal(String input) {int n;String[] line = input.split("\n");n = Integer.parseInt(line[0]); // 10String[] nums = line[1].split(" ");for (int x = 1; x <= n; x++)a[x] = Integer.parseInt(nums[x - 1]);build(1, n, 1);int count = 2;while (true) {String[] command = line[count++].split(" ");if (command[0].equals("End")) break;int i = Integer.parseInt(command[1]);int j = Integer.parseInt(command[2]);if (command[0].equals("Query")) {output += query(i, j, 1, n, 1) + "\n";} else if (command[0].equals("Sub")) {update(i, -j, 1, n, 1);} else {update(i, j, 1, n, 1);}}return output;}
}