创建网站需要哪些步骤,典型的电子商务网站,建设钓鱼网站,配音秀做素材网站树状数组#xff0c;也叫Fenwick Tree和BIT(Binary Indexed Tree)#xff0c;是一种支持单点修改和区间查询的#xff0c;代码量小的数据结构。
那神马是单点修改和区间查询#xff1f;我们来看一道题。
洛谷P3374(模板): 在本题中#xff0c;单点修改就是将某一个数加上…树状数组也叫Fenwick Tree和BIT(Binary Indexed Tree)是一种支持单点修改和区间查询的代码量小的数据结构。
那神马是单点修改和区间查询我们来看一道题。
洛谷P3374(模板): 在本题中单点修改就是将某一个数加上x的操作区间查询就是求出某区间每一个数的和的操作这下明白了吧。
下面来解释一下树状数组的工作原理。先看一张图(来源于OI-Wiki)
Tips:别找了点一下图那个字就有了。
我们发现树状数组总能将一段前缀拆成不多于段区间使得这几段区间的信息是已知的。因此我们只用合并这些区间的信息就可以得到答案。因此时间复杂度从变成效率大大提高。
管辖区间
我们观察刚刚的图发现每个相当于一个小leader掌管自己的范围。那这个范围是多少呢我们规定管辖的区间长度为其中k为x的二进制表示中最低位的1所在的二进制位数。而为x的二进制表示中最低位的1以及后面所有0组成的数。即管辖的区间是。注意:lowbit(x)表示这个1和后面所有0组成的。
下面附上OI-Wiki中对lowbit(x)的原理的解释(其实是我不会解释)
将 x 的二进制所有位全部取反再加 1就可以得到 -x 的二进制编码。例如 的二进制编码是 110全部取反后得到 001加 1 得到 010。
设原先 x 的二进制编码是 (...)10...00全部取反后得到 [...]01...11加 1 后得到 [...]10...00也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1 是 x 最低位的 1。
(...) 和 [...] 中省略号的每一位分别相反所以 x -x (...)10...00 [...]10...00 10...00得到的结果就是 lowbit。
//lowbit的实现
int lowbit(int x){return x(-x);
}
lowbit可以说是一个很经典的二进制运算了。
区间查询
经过上面的分析我们可以知道回答区间查询的步骤了:
· 从往前跳一直让就行了。
· 如果x0就结束循环
· 将跑到的累加
实现如下↓:
int get_sum(int x){int sum0;while(x0){sumc[x];x-lowbit(x);}return sum;
}
单点修改
也很简单。
· 先修改
· 然后一直让让
· 如果xn就结束循环
实现如下↓:
void modify(int x,int y){while(xn){c[x]y;xlowbit(x);}
}
洛谷P3374(模板):
那这题就很easy啦~
#include bits/stdc.h
using namespace std;
int c[maxn];
int n,m;
int lowbit(int x){return x(-x);
}
void modify(int x,int y){while(xn){c[x]y;xlowbit(x);}
}
int get_sum(int x){int res0;while(x0){resc[x];x-lowbit(x);}return res;
}
int main(){cinnm;for(int i1;in;i){int x;cinx;modify(i,x);}for(int i1;im;i){int op,x,y;cinopxy;if(op1)modify(x,y);if(op2)coutget_sum(y)-get_sum(x-1)endl;}return 0;
}
别走啊这不得在找几题练练
逆序对:
基础题。现在按照序列从左到右将数据的值对应的位置的数加一代表又有一个数出现。因此在循环到第i项时前i-1项已经加入到树状数组内了树状数组内比大的都会与构成逆序对因为它们一定出现的更早所以产生的逆序对数量为。要注意的是我们需要进行离散化因为根据建树确实不够。然后就是代码部分啦。
#include bits/stdc.h
using namespace std;
pairlong long,long long a[maxn];
long long b[maxn],c[maxn];
int n;
int lowbit(int x){return x(-x);
}
void modify(int x){while(xn){c[x];xlowbit(x);}
}
int get_sum(int x){int sum0;while(x0){sumc[x];x-lowbit(x);}return sum;
}
int main(){cinn;for(int i1;in;i){cina[i].first;a[i].secondi;}sort(a1,an1);for(int i1;in;i)b[a[i].second]i;long long ans0;for(int in;i;i--){ansget_sum(b[i]);modify(b[i]);}coutansendl;return 0;
}
当然用归并也是Ok的。
火柴排队:
一道非常非常经典的题目。我们乍一看就是让我们最小化也就是最小化也就是a序列第k大的元素必须和序列b中第k大的元素的位置必须一样。OK,那我们把a,b离散化问题变成了b序列要交换几次可以令其等于a。我们令相当于以为关键字对序列排序如果a和b一样那么。那么我们需要让q升序排列。问题又变成将原本乱的 q序列升序排列的最少交换次数。
诶这不就是逆序对吗
用树状数组或归并即可。这里给归并的代码树状数组的参考上面P1908的代码。
#include bits/stdc.h
using namespace std;
int a[maxn],b[maxn];
int c[maxn],d[maxn];
int num1[maxn],num2[maxn];
int calc[maxn];
long long ans0;
int tmp[maxn];
void msort(int l,int r){if(lr)return;int mid(lr)1;msort(l,mid);msort(mid1,r);int il,jmid1;int kl;while(imid jr){if(a[i]a[j])tmp[k]a[i];else{tmp[k]a[j];ansmid-i1;ans%MOD;}}while(imid)tmp[k]a[i];while(jr)tmp[k]a[j];for(int il;ir;i)a[i]tmp[i];
}
int main(){int n;cinn;for(int i1;in;i){cina[i];c[i]a[i];}for(int i1;in;i){cinb[i];d[i]b[i];}sort(d1,dn1);for(int i1;in;i)num1[d[i]]i;sort(c1,cn1);for(int i1;in;i)num2[c[i]]i;for(int i1;in;i)calc[num1[b[i]]]i;for(int i1;in;i)a[i]calc[num2[a[i]]];msort(1,n);coutans%MODendl;return 0;
}
别忘了取模哦。
The Last Problem:ABC157E
此题一看就是树状数组。但是由于有26个字母我们要建26个树状数组每一个存放该字母出现的位置。这样在询问的时候直接查询每一个树状数组的[l,r]的和如果这个和0那么就把 ans加1最后输出即可。
#include bits/stdc.h
using namespace std;
int c[26][500005];
int lowbit(int x){return x(-x);
}
void update(int c[],int x,int val){while(x500000){c[x]val;xlowbit(x);}
}
int getsum(int c[],int x){int sum0;while(x0){sumc[x];x-lowbit(x);}return sum;
}
int main(){int n;cinn;string str;cinstr;str str;for(int i1;in;i)update(c[str[i]-a],i,1);int q;cinq;while(q--){int op;cinop;if(op1){int x;char ch;cinxch;update(c[str[x]-a],x,-1);update(c[ch-a],x,1);str[x]ch;}if(op2){int l,r;cinlr;int ans0;for(int i0;i26;i){if(getsum(c[i],r)-getsum(c[i],l-1))ans;}coutansendl;}}return 0;
}
Ok,以上就是本期的全部内容了。我们下期再见!
温馨提示:本期的所有代码都有问题请不要无脑Ctrl CCtrl V(你会挂的很惨)看懂了自己写一遍
