问题引入：http://nyoj.top/problem/116
https://www.cnblogs.com/Howe-Young/p/4009223.html?ADUIN=1466989448&ADSESSION=1413411257&ADTAG=CLIENT.QQ.5359_.0&ADPUBNO=26397
树状数组详解： https://www.cnblogs.com/George1994/p/7710886.html
树状数组区间查询：https://blog.csdn.net/qq_21841245/article/details/43956633
树状数组lowbit讲解：https://www.cnblogs.com/circlegg/p/7189676.html
树状数组非常玄妙，核心在于lowbit，复杂度为log（n），二分的复杂度，树状数组也称二叉索引树。复杂度的期望值是比线段树低，代码比线段树简单很多，可是在解题范围上，线段树要比较大。
其中tem[x]代表的是原数组区间【x-lowbit(x)+1,x】的和。所以，查询区间【x-lowbit(x)+1,x】,a=x-lowbit(x).......【a-lowbit(a)+1,a】...（a>0）的和就是答案
lowbit（）函数：函数用于找到最低位一的位置，其实树状数组的储存方法就是二进制，方法很玄妙。
#include<algorithm> #include<string.h> #include<stdio.h> using namespace std; int tem[1000000]; int n,m; int lowbit(int v) { return v&-v; } void add(int v,int e) { while(v<=n) { tem[v]+=e; v+=lowbit(v); } } int sum(int n) { int ans=0; while(n>0) { ans+=tem[n]; n-=lowbit(n); } return ans; } int main() { int l,r,x; char str[50]; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); add(i,x); } while(m--) { scanf("%s%d%d",str,&l,&r); if(!strcmp(str,"QUERY")) { printf("%d\n",sum(r)-sum(l-1)); } else { add(l,r); } } }
