其实很容易理解就是询问一段区间内有多少段不同的区间
然后再仔细思索一下会发现：
1.只要一个区间的开头在一个节点i的左边，那么这个区间包含在区间1~i中。
2.只要一个区间的尾部在一个节点j的左边，那么这个区间肯定不属于j之后的所有区间
这时候就不难想到用两个树状数组维护：
第一个：维护节点i之前有多少个区间的开头
第二个：维护节点j之前有多少个区间的结尾
不难证明拿sum[i]-sum[j]得到的就是i~j中间地雷的个数(手动模拟一波就一清二楚了)
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<iomanip> #include<algorithm> #include<stack> #include<queue> #define lst long long #define rg register #define N 100050 using namespace std; int n,m; lst ans; int tou[N],wei[N];//tou存前面有多少个区间的开始，以下简称头部树状数组 //wei存前面有多少个区间的尾部，以下简称尾部树状数组 //类似于前缀和 inline int read()//读入优化 { rg int s=0,m=1;rg char ch=getchar(); while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar(); if(ch==‘-‘)m=-1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar(); return s*m; } //以下是树状数组的板子 inline int lowbit(rg int kk)//lowbit { return kk&(-kk); } inline void add_tou(rg int kk)//加入树状数组的头部数组 { while(kk<=n) { ++tou[kk]; kk+=lowbit(kk); } } inline void add_wei(rg int kk)//加入树状数组的尾部数组 { while(kk<=n) { ++wei[kk]; kk+=lowbit(kk); } } inline int sum_tou(rg int kk)//计算节点前有多少个区间的开始 { rg int s=0; while(kk>0) { s+=tou[kk]; kk-=lowbit(kk); } return s; } inline int sum_wei(rg int kk)//计算节点前有多少个区间的结束 { rg int s=0; while(kk>0) { s+=wei[kk]; kk-=lowbit(kk); } return s; } int main() { n=read(),m=read();//读入 for(rg int i=1;i<=m;++i) { rg int sign=read(); rg int x=read(),y=read();//读入 if(sign==1) { add_tou(x);//加入头部树状数组 add_wei(y);//加入尾部树状数组 } else { ans=sum_tou(y)-sum_wei(x-1);//运用已经证明的规律结题 printf("%d\n",ans); } } return 0; }
通过这道题，我们可以发现大部分的树状数组题目可以用线段树做，但也有线段树不好维护的题目，这就需要灵活的利用树状数组的技巧(虽然题解里也有线段树比较好理解的) 我自认为我的代码还是蛮好看的，只是变量有点丑，但好理解
原文：https://www.cnblogs.com/cjoierljl/p/8783506.html