集训时摸的鱼都是今天的泪。
问题背景：一个序列，求相同两个字母之间不同字母的个数。
问题延伸：求区间内不同数字的个数。
结合《挑战》与树状数组彻底入门，算法清脆的电话都看得懂的超详细解析
树状数组的原理与实现
BIT的原理
把线段树不需要的右儿子都扔掉了
为什么要利用lowbit函数？对树状数组有什么作用么？那么我们仍然利用上面的表格，得到这样的图：
如果把lowbit函数的值作为这个位置储存的区域和，这样就可以完美覆盖所有位置。也就是，每一个数字管理一段区间。就像线段树一样。这就是为什么我们要利用lowbit函数。
我们在维护、使用树状数组的时候，利用累加。原来数组上利用累加的时候是i++，这样遍历一次数组时间复杂度为O(n)，我们既然可以利用lowbit，那么累加的时候将i++改为i += lowbit(i)，这样虽然我们还是在原数组上跳跃，但是可以抽象成在一个树上按顺序遍历。
https://blog.csdn.net/iwts_24/article/details/82497026
BIT的结构
BIT使用数组维护下图所示的部分和
直观地看，最后有k个连续的0，区间长度就为k,维护的值就是包括自己往前数2^k个。
1000 c[8]=a[8]+…+a[1]
0111 c[7]=a[7]
0110 c[6]=a[6]+a[5]
0101 c[5]=a[5]
BIT的求和
区间查询
利用C[i]数组，来求A数组前i项的和
sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ; 前i项和
C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];
可以推出: sum[7]=C[4]+C[6]+C[7];
序号写为二进制: sum[(111)]=C[(100)]+C[(110)]+C[(111)];
111
110 （111-1，111-2^0）
100 （110-10, 110-2^1）
0 （100-100，100-2^2）
sum[5]=A[1]+A[2]+A[3]+A[4]+A[5] ; 前i项和
C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5];
可以推出: sum[5]=C[4]+C[5];
序号写为二进制: sum[(101)]=C[(100)]+C[(101)];
101
100 （101-1，101-2^0）
0 （100-100，100-2^2）
int lowbit(int x){ return x&(-x);}int getsum(int x) //x是下标{ int sum=0; while(x) { sum+=low[x]; x-=lowbit(x); } return sum;} BIT值的更新
1000 c[8]=a[8]+…+a[1]
0111 c[7]=a[7]
0110 c[6]=a[6]+a[5]
0101 c[5]=a[5]
我们看到，c[5]的值被c[6],c[8]用到了，因此在更新c[5]的时候要同步更新c[6]和c[8]，这是个反向的操作
c[7]只需要set自己
也就是说从小到大通过加lowbit的方式，只更新包含自己的区间~
//n是序列总数void update(int x,int val){ while(x<=n) { low[x]+=val; x+=lowbit(x); }}101 + 1 = 110110 + 10 = 10001000 + 1000 = 10000
加上或减去lowbit()，都是使末尾的0更多的操作
求区间内不同数字的个数
思路：维护前i个数中不同数字的个数，那么做个区间的差即可。如何维护不同的数字个数呢，那就是只记录在最后一次出现的位置。第一次出现的时候，在出现的位置update(位置,1)，把该位置记做pre。数字再次出现的时候，update(pre,-1),当前位置再加1。那么同一个文件就只算了一次。注意当我在update(pre,-1)时，破坏了之前的结果，因此我们要按照查询区间的右端点来排序，当扫到右端点的时候，就计算一次答案。
手痒痒了orz
贴个别人的代码留个印象
添加链接描述
#include<cstdio>#include<algorithm>#include<cstring>using namespace std; const int maxn=100010;int num[maxn]; ///存储数列int tree[maxn]; ///树状数组int book[maxn];int out[maxn]; ///存储结果int N; struct node{ int l,r; int pos;}ask[maxn]; ///存储询问数组 bool cmp(node x,node y) ///按 r 从小到大排序{ return x.r<y.r;} int lowbit(int n) ///树状数组{ return n&(-n);} void add(int n,int v) ///更新值{ while(n<=N) { tree[n]+=v; n+=lowbit(n); } return;} int sum(int n) ///树状数组求前n个结果{ int result=0; while(n) { result+=tree[n]; n-=lowbit(n); } return result;}int main(){ int Q; while(~scanf("%d%d",&N,&Q)) { memset(book,0,sizeof(book)); memset(tree,0,sizeof(book)); memset(out,0,sizeof(out)); for(int i=1;i<=N;i++) scanf("%d",&num[i]); for(int i=1;i<=Q;i++){ scanf("%d%d",&ask[i].l,&ask[i].r); ask[i].pos=i; ///因为下面要排序，为了记忆，故要标记下是第几个 } sort(ask+1,ask+1+Q,cmp); int temp=1;///看似二重循环，其实也只是从小到大扫了一遍 ///因为值r已经排好序了，故j是从1开始，一直要最大的r。 for(int i=1;i<=Q;i++) { for(int j=temp;j<=ask[i].r;j++) { if(book[num[j]]) ///之前有出现过，在之前的位置减1 { add(book[num[j]],-1); } add(j,1); /// 在这个位置加1 ，为什么加的是1呢，因为我们算的是不同数字的个数， ///不是值的和，跟刚开始入门树状数组中求的和的有些不同的。 book[num[j]]=j;///用book数组存储值num[j] 的位置 } temp=ask[i].r+1; ///表示下次开始的位置 out[ask[i].pos]=sum(ask[i].r)-sum(ask[i].l-1);///用out数组存储每组询问的结果 } for(int i=1;i<=Q;i++) ///输出结果 printf("%dn",out[i]); } return 0;}