数据结构基础

【题目描述】太空堡垒（fort）HDU 1166

小光的太空舰队在太空中沿直线布置了N个太空堡垒，由于琳琳的舰队采取了某种先进的监测手段，所以小光的每个堡垒的飞船数琳琳都掌握的一清二楚，每个堡垒的飞船数都有可能发生变动，可能增加或减少若干飞船，但这些都逃不过琳琳舰队的监视。

作为演习总指挥的琪儿，需要经常了解某一段连续的堡垒一共有多少飞船，例如琪儿问：“红方指挥官，马上汇报第3个堡垒到第10个堡垒共有多少飞船!”红方指挥官琳琳就要派你马上开始计算这一段的总飞船数并汇报。但堡垒的飞船数经常变动，而琪儿每次询问的段都不一样，所以你不得不每次一个一个的数，因此很快就精疲力尽了，为了避免这种情况的发生，你能写个程序完成这项工作吗？

【输入格式】

第一行一个整数T，表示有T组数据。

每组数据第一行一个正整数N（N≤50 000），表示有N个堡垒，接下来有N个正整数，第i个正整数a_i代表第i个堡垒里开始时有a_i个飞船（1≤a_i≤50）。

接下来每行有一条命令，命令有4种形式：

（1）Add i j，i和j为正整数，表示第i个堡垒增加j个飞船（j不超过30）

（2）Sub i j，i和j为正整数，表示第i个堡垒减少j个飞船（j不超过30）

（3）Query i j，i和j为正整数，i≤j，表示询问第i到第j个堡垒的总飞船数

（4）End 表示结束，这条命令在每组数据最后出现

每组数据最多有40 000条命令。

【输出格式】

对第i组数据，首先输出“Case i:”和回车，对于每个Query询问，输出一个整数并回车，表示询问的段中的总飞船数，这个数保持在32位int取值范围之内。

【输入样例】

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

【输出样例】

Case 1:

6

33

59