区间树状数组

具体参数见注释.首先是设定：

设定一：朴素树状数组不能沟进行足够快的区间更新
设定二：我本人懒得写线段树

于是我们有了“可以足够快进行区间更新”的树状数组。

对于任意前N项和（记为SUM(N)）都应当有SUM(N)=A[1]+A[2]+A[3]+........+A[N]。
设C[K]=A[K]-A[K-1]都应该有：SUM[C[N]]=A[N]:
证明：
A：SUM[C[N]]=C[1]+C[2]+C[3]+C[4]+.......+C[N];
B：SUM[C[N]]=-A[0](A[0]不存在有意义的值，认为是0)+A[1]+(A[2]-A[1])+(A[3]-A[2]).......+(A[N]-A[N-1])=A[N]
推论：SUM[A[N]]=A[1]+A[2]+A[3]+.....+A[N]=SUM(C[1])+SUM(C[2])+SUM(C[3])+......+SUM(C[N])
展开得：=SUM[A[N]]=N*C[1]+(N-1)*C[2]+......+C[N]->进行一个巧妙地变换，我们可以把系数对应起来：
SUM[A[N]]=N*SUM[C[N]]-0*C[1]-1*C[2]-........(N-2)*C[N-1];
于是另外设定一个数组：C2并且认为C2[K]=(K-1)*C[K]于是，我们得到了一种数组求和的等效替代，对原数组的仇和操作作都可以被分解为对于C和C2的求和操作。
（未完待续。。。。）

 1 /*
 2 *常量MAXN用于设定树状数组的尺寸大小
 3 */
 4 const long long MAXN=500233;
 5 class TreeLikeArray
 6 {
 7     public:
 8 /*
 9 *数组c1用来储存A[i]-A[i-1]；
10 */
11         long long c1[MAXN];
12 /*
13 *数组c2用来储存(A[i]-A[i-1])*(i-1)；
14 *或认为用于储存(i-1)*c1[i]；
15 *两种实现方式完全等价
16 */
17         long long c2[MAXN];
18 /*
19 *树状数组的常规操作，参数要求传入数组并指明更新位置，以及更新参数。
20 *树状数组基础底层操作
21 */
22         void add(long long array[],long long pos,long long key)
23     {
24         while(pos<MAXN)
25         {
26             array[pos]+=key;
27             pos+=pos&(-pos);
28         }
29     }
30 /*
31 *特别树状数组单点更新操作，要求传入位置和参数
32 */
33     void add(long long pos,long long key)
34     {
35         add(c1,pos,key);
36         add(c1,pos+1,-key);
37         add(c2,pos,(pos-1)*key);
38         add(c2,pos+1,-pos*key);
39     }
40 /*
41 *特别树状数组多点更新操作，要求传入起始位置、终止位置和参数
42 *该操作将会使得[pos1,pos2]闭区间内所有元素得到更新
43 */
44     void add(long long pos1,long long pos2,long long key)
45     {
46         add(c1,pos1,key);
47         add(c1,pos2+1,-key);
48         add(c2,pos1,(pos1-1)*key);
49         add(c2,pos2+1,-pos2*key);
50     }
51 /*
52 *树状数组的常规操作，参数要求传入数组并指明求和位置
53 *树状数组基础底层操作
54 */
55     long long getSum(long long array[],long long pos)
56     {
57         long long ret=0;
58         while(pos>0)
59         {
60             ret+=array[pos];
61             pos-=pos&(-pos);
62         }return ret;
63     }
64 /*
65 *从起始节点到目标节点闭区间求和[0,i]
66 */
67     long long getSum(long long pos)
68     {
69         return pos*getSum(c1,pos)-getSum(c2,pos);
70     }
71 /*
72 *求[pos1,pos2]闭区间内元素和
73 */
74     long long getSum(long long pos1,long long pos2)
75     {
76         return getSum(pos2)-getSum(pos1-1);
77     }
78 /*
79 *求pos单个元素的值
80 */
81     long long getSingle(long long pos)
82     {
83         return getSum(pos,pos);
84     }
85 };