树状数组线段树

目录一树状数组二进制优化的前缀和1.应用2.时间复杂度3.思路4.模板题5.模板6.模板题27.模板2二.线段树进阶树状数组1.应用2.时间复杂度3.思路4.模板题5.模板一树状数组二进制优化的前缀和1.应用在不断修改数据的情况下求区间和2.时间复杂度查询O(log n)修改O(log n)3.思路1(1)修改树状数组在前缀和的基础上进行了优化。c[i]只管理包括i在内向前推lowbit(i)长度的区间和lowbit是指i的二进制的最低一位1所对应的十进制可以用i(-i)得出。这样的话修改c[i]只需要将管理c[i]的点修改一遍即可为O(log n)(2)查询要想得到1 - i区间的前缀和我们只需要每次更新i为i - lowbit(i)并递归到1把所有访问到的c[i]加和即可为O(log n)。4.模板题1P3374 【模板】树状数组 1 - 洛谷 改单求区5.模板1#includebits/stdc.h using namespace std; const int N5e510; int n,m; int a[N],c[N]; void add(int x,int y){ while(xn){ c[x]y; x(x(-x)); } } int query(int x){ int ans0; while(x0){ ansc[x]; x-(x(-x)); } return ans; } int main(){ cinnm; for(int i1;in;i){ cina[i]; add(i,a[i]); } while(m--){ int op,x,y,k; cinop; if(op1){ cinxk; add(x,k); } else{ cinxy; int ansquery(y)-query(x-1); coutansendl; } } return 0; }6.模板题2P3368 【模板】树状数组 2 - 洛谷 改区求单7.模板2#includebits/stdc.h using namespace std; const int N1e610; long long n,m; int a[N]; int c[N]; //shuzhangshuzu int d[N]; int query(int x){ //1-x的和 int sum0; while(x0){ sumc[x]; x-(x(-x)); } return sum; } void add(int x,int y){ while(xn){ c[x]y; x(x(-x)); } } int main(){ cinnm; for(int i1;in;i){ cina[i]; add(i,a[i]-a[i-1]); } while(m--){ int op; cinop; if(op1){ int x,y,k; cinxyk; add(x,k); add(y1,-k); } else{ int x; cinx; int ansquery(x); coutansendl; } } return 0; }二.线段树进阶树状数组1.应用专门解决单点修改区间求和问题2.时间复杂度查询O(log n)修改O(log n)但常数大3.思路(1)先构建一棵满二叉搜索树节点u的l是u1r是u1|1。节点u统计区间x ~ y的和则l管x ~ midr管mid1 ~ r(2)查询从根节点一直扩展如果某个节点管辖的范围根本不在需要查询的区间内则无需扩展否则如果某个节点管辖区间完全被包含在区间内直接加和——O(log N)(3)修改扩展方式同上。但是有一个问题如果对节点u直接添加元素会使得其子树无法继承。那么我们就引入了一个懒标。我们将u点的每次叠加其子树以后如果想要操作就把懒标记传下去。都传完之后对其进行清零。这样之后每次访问到的点都加上懒标——O(log N)4.模板题P3372 【模板】线段树 1 - 洛谷 (改区求区)5.模板#includebits/stdc.h using namespace std; #define int long long const int N2e610; int n,m; int a[N]; int tree[N]; int lazy[N]; void pushdown(int o,int l,int r){ int mid(lr)/2; if(lazy[o]){ lazy[o*2]lazy[o]; lazy[o*21]lazy[o]; tree[o*2](mid-l1)*lazy[o]; tree[o*21](r-mid)*lazy[o]; lazy[o]0; } } void build(int o,int l,int r){ if(lr){ tree[o]a[l]; return ; } long long mid(lr)/2; build(o*2,l,mid); build(o*21,mid1,r); tree[o]tree[o*2]tree[o*21]; } void update(int o,int l,int r,int x,int y,int val){ if(lx ry){ tree[o](r-l1)*val; lazy[o]val; return; } int mid(lr)/2; pushdown(o,l,r); if(xmid){ update(o*2,l,mid,x,y,val); } if(ymid){ update(o*21,mid1,r,x,y,val); } tree[o]tree[o*2]tree[o*21]; } int query(int o,int l,int r,int x,int y){ if(xl yr){ return tree[o]; } int mid(lr)/2,ans0; pushdown(o,l,r); if(xmid){ ansquery(o*2,l,mid,x,y); } if(ymid){ ansquery(o*21,mid1,r,x,y); } return ans; } signed main(){ cinnm; for(int i1;in;i){ cina[i]; } build(1,1,n); while(m--){ int op,x,y; cinopxy; if(op1){ int k; cink; update(1,1,n,x,y,k); } else{ coutquery(1,1,n,x,y)endl; } } return 0; }