题目描述（HDU1166）： A国在海岸线沿直线布置了 N 个工兵营地。C国通过先进的监测手段对A国每个工兵营地的人数都掌握得一清二楚。每个工兵营地的人数都可能发生变动，可能增加或减少若干人手。

输入： 第1行包含一个整数 T ，表示有 T 组数据。每组数据的第1行都包含一个正整数 N （ N ≤50000），表示有 N 个工兵营地。接下来有 N 个正整数，第 i 个正整数 a i 代表第 i 个工兵营地开始时有 a i 个人（1≤ a i ≤50）。再接下来每行都有一条命令，每组数据最多有40000条命令，命令有4种形式：①Add i j ，表示第 i 个营地增加 j 个人（ j ≤30）；②Sub i j ，表示第 i 个营地减少 j 个人（ j ≤30）；③Query i j ， i ≤ j ，表示查询第 i ～ j 个营地的总人数（int以内）；④End，表示结束，在每组数据的最后出现。命令中的 i 和 j 均为正整数。

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

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

1. 算法设计

（1）创建线段树，存储区间和。

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

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

创建线段树时可以采用存储区间信息和不存储区间信息两种方法，本题采用不存储区间信息的方法创建线段树，并对两种区间查询方法进行对比。

2. 创建线段树的两种方法

创建线段树的方法不同，数据结构和区间查询时的参数也不同。

（1）节点存储区间信息。每个节点都存储区间信息 l 、 r ，以及其他信息如最值或和值。在前面线段树的基本操作中就采用了这种方式，进行区间查询时只需3个参数：待查询区间 L 、 R 和当前节点的编号。

（2）节点不存储区间信息。每个节点都不存储区间信息 l、r ，用数组存储其他信息如最值或和值。进行区间查询时需要5个参数：待查询区间 L 、 R ；当前节点的 l 、 r ；当前节点编号 rt 。节点不存储区间信息构建线段树的代码如下，区间查询的代码在后面给出。

3. 区间查询的两种方法

无论采用哪种方法创建线段树，都可以采用区间覆盖和区间相等两种方法进行区间查询。以节点不存储区间信息的5个参数区间和查询为例，3个参数类似。

（1）区间覆盖。判断条件为覆盖时，查询区间无须改变，一直是[ L , R ]，累加左右两个区间查询的和值。

（2）区间相等。判断条件为相等且跨两个区间查询时，左右子树的查询范围分别变为[ L , m ]、[ m +1, R ]。 C0GAlDf75eTOKytok/yoS5tjvasG/sEha/1w8QE3wYKLr+0YcZesWMNKE6XWdB60