士兵杀敌（四）
时间限制：2000 ms | 内存限制：65535 KB
难度：5
- 描述
-
南将军麾下有百万精兵，现已知共有M个士兵，编号为1~M，每次有任务的时候，总会有一批编号连在一起人请战（编号相近的人经常在一块，相互之间比较熟悉），最终他们获得的军功，也将会平分到每个人身上，这样，有时候，计算他们中的哪一个人到底有多少军功就是一个比较困难的事情，军师小工的任务就是在南将军询问他某个人的军功的时候，快速的报出此人的军功，请你编写一个程序来帮助小工吧。
假设起始时所有人的军功都是0.
- 输入
- 只有一组测试数据。
每一行是两个整数T和M表示共有T条指令，M个士兵。（1<=T,M<=1000000)
随后的T行，每行是一个指令。
指令分为两种：
一种形如
ADD 100 500 55 表示，第100个人到第500个人请战，最终每人平均获得了55军功，每次每人获得的军功数不会超过100，不会低于-100。
第二种形如：
QUERY 300 表示南将军在询问第300个人的军功是多少。 - 输出
- 对于每次查询输出此人的军功，每个查询的输出占一行。
- 样例输入
-
4 10 ADD 1 3 10 QUERY 3 ADD 2 6 50 QUERY 3
- 样例输出
-
10 60
这题用树状数组来做，是叫插线问点吧，已经有很多博文写了，代码很简单，可是都只有代码，这里我就说说我自己的理解吧。
当要给从from到to的士兵加军功e的时候，就给(1,from-1)的士兵加-e的军功，给(1,to)的士兵加军功。（Add函数）
根据树状数组的特性，当给某段士兵加军功时，数组中不是每个士兵的军功值都会变化，比如下图（图来自百度百科）中，当从4开始减少e1军功时，1，2，3中是不变的，只有4减少了e1,当从8开始-e2时，1到7都不变，只有8减少了e2，增加军功e3是相同的道理，所以当要查询3时，所以要对其父节点4、8……求和。（GetSum函数）
总结起来就是
1 父节点的变化反映了其下子节点的变化
2 子节点的值由其不同维度的父节点决定（4是3的父节点，8也是3父节点，16也是3的父节点……）
具体代码如下（都大同小异）：
#include
<cstdio>02.using namespace std;03. 04.#define
MAXN 100001005.int me[MAXN],M;06. 07.void Add(int x,int val)08.{09.while(x)10.{11.me[x]+=val;12.x-=x&(-x);13.}14.}15. 16.int GetSum(int x)17.{18.int sum=0;19.while(x<=M)20.{21.sum+=me[x];22.x+=x&(-x);23.}24.return sum;25.}26. 27.int main()28.{29.char command[6];30.int T,from,to,e;31.scanf("%d%d",&T,&M);32.while(T--)33.{34.scanf("%s",command);35.if(command[0]=='A')36.{37.scanf("%d%d%d",&from,&to,&e);38.Add(from-1,-e);39.Add(to,e);40.}41.else42.{43.scanf("%d",&from);44.printf("%d\n",GetSum(from));45.}46.}47.return 0;48.}