做恒指网站,wordpress文章html,godaddy wordpress 2014,做电台需要的文章从哪个网站找文章目录 什么是树状数组#xff1f;如何理解树状数组如何理解精髓lowbit二叉树和树状数组的结构树状数组的优点树状数组模板单点修改#xff0c;区间查询区间修改#xff0c;单点查询区间修改#xff0c;区间查询树状数组法线段树法 树状数组基础练习题逆序对动态求连续区… 文章目录 什么是树状数组如何理解树状数组如何理解精髓lowbit二叉树和树状数组的结构树状数组的优点树状数组模板单点修改区间查询区间修改单点查询区间修改区间查询树状数组法线段树法 树状数组基础练习题逆序对动态求连续区间和数星星校门外的树简单题打鼹鼠 什么是树状数组 和并查集一样树状数组和线段树都是算法竞赛中常见的数据结构他们通常结构清晰操作方便应用灵活效率很高。
如何理解树状数组
一句话概括树状数组可以高效率的查询和维护前缀和或区间和 所谓前缀和即给出长度为n的数列A{ a 1 , a 2 , a 3 , . . . . , a x a_1,a_2,a_3,....,a_x a1,a2,a3,....,ax}和一个查询 x n xn xn求 s u m ( x ) a 1 a 2 … a x sum(x)a_1a_2…a_x sum(x)a1a2…ax。数列 [ i j ] [ij] [ij]区间和通过前缀和求得即ai…ajsum(j)-sum(i-1)。 如果数列A是静态不变的代码很好写预处理前缀和就好了一次预处理的复杂度为0(n然后每次查询复杂度都为O(1)。但是如果序列是动态变化的如改变其中一个元素a的值那么它后面的前缀和都会改变需要重新计算如果每次查询前元素都有变化那么一次查询的复杂度就变为On。
如何理解精髓lowbit
lowbit(x)x-x,功能是找x的二进制最后一个1原理是用到了负数的补码。下面这两张张表可能能更好的让你理解为什么树状数组这样构造以及他的基础函数的由来 二叉树和树状数组的结构 上述图片给我们展示了二叉树到树状数组的结构变换有助于我们更好的理解树状数组。
树状数组的优点
优点修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小并且实现比线段树简单
缺点扩展性弱线段树能解决的问题树状数组不一定能解决.
树状数组模板
万变不离其宗这两个函数是树状数组的精髓要好好掌握。
void update (int x,int k) {while (xN) {tree[x]k;xlowbit(x);}
}
int query (int x) {int ans0;while (x0) {anstree[x];x-lowbit(x);}return ans;
}关于如何理解树状数组可以结合有关资料学习这里只给出模板并给出一些练习题帮助更好的理解树状数组
单点修改区间查询
const int N 1e65;
int a[N],b[N];
int tree[N];
int n,m;void solve ()
{cinnm;for (int i1;in;i) {int x;cinx;update(i,x);}for (int i1;im;i) {int pos,x,y;cinposxy;if(pos1) {update(x,y);}else {coutquery (y)-query (x-1)\n;}}return ;
}区间修改单点查询
区间修改单点查询的模板用到了差分数组不懂差分的可以去查询有关资料
const int N 1e65;
int a[N],b[N];
int chafen[N];
int tree[N];
int n,m;void solve ()
{cinnm;for (int i1;in;i) {cinchafen[i];int xchafen[i]-chafen[i-1];update(i,x);}for (int i1;im;i) {int pos,x,y,k;cinpos;if(pos1) {cinxyk;update(x,k);update(y1,-k);} else {cinx;coutsum(x)\n;}}return ;
}区间修改区间查询
这部分代码有些难以实现运用到了数学的相互转换。区间修改区间查询是线段树的强项。我把两种方法都贴出来以供参考
树状数组法
#include bits/stdc.h
#define lowbit(x) (x(-x))
using namespace std;
const int N 1e65;
int a[N],b[N];
int tree1[N],tree2[N];
int m,n;void update1 (int x,int k) {while (xn) {tree1[x]k;xlowbit(x);}
}void update2 (int x,int k) {while (xn) {tree2[x]k;xlowbit(x);}
}int sum1 (int x) {int res0;while (x0) {restree1[x];x-lowbit(x);}return res;
}int sum2 (int x) {int res0;while (x0) {restree2[x];x-lowbit(x);}return res;
}void solve () {cinmn;for (int i1;im;i) {cina[i];int xa[i]-a[i-1];update1 (i,x);update2 (i,(i-1)*x);}for (int i1;in;i) {int pos;cinpos;if (pos1) {int x,y,k;cinxyk;update1(x,k);update1(y1,-k);update2(x,k*(x-1));update2(y1,-k*y);}else {int x,y;cinxy;int ans1y*sum1(y)-sum2(y);int ans2(x-1)*sum1(x-1)-sum2(x-1);coutans1-ans2\n;}}
}线段树法
#include bits/stdc.h
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N 1e55;
int a[N];
int tree [N2],tag[N2];int ls (int p) {return p1;}
int rs (int p) {return p1|1; }void push_up (int p) {tree[p]tree[ls(p)]tree[rs(p)];
// tree[p]min (tree[ls(p)],tree[rs(p)]);//Çó×îСֵµÄʱºòpush_upº¯ÊýÀïÃæÊÇÕâ¸ö
}void build (int p,int pl,int pr) {tag[p]0;if (plpr) {tree[p]a[pl];return ;}int mid (plpr)1;build (ls(p),pl,mid);build (rs(p),mid1,pr);push_up(p);
}void addage (int p,int pl,int pr,int d) {tag[p] d;tree[p] d*(pr-pl1);
}void push_down (int p,int pl,int pr) {if (tag [p]) {int mid (plpr)1;addage (ls(p),pl,mid,tag[p]);addage (rs(p),mid1,pr,tag[p]);tag[p]0;}
}void update (int l,int r,int p,int pl,int pr,int d) {if (l pl pr r) {addage (p,pl,pr,d);return ;}push_down(p,pl,pr);int mid(plpr)1;if (l mid) update (l,r,ls(p),pl,mid,d);if (r mid) update (l,r,rs(p),mid1,pr,d);push_up (p);
}int query (int l,int r,int p,int pl,int pr) {if (pllprr) return tree[p];push_down (p,pl,pr);int res0;int mid (plpr)1;if (lmid) res query (l,r,ls(p),pl,mid);if (rmid) res query (l,r,rs(p),mid1,pr);return res;
}void solve () {int n,m;cinnm;for(int i1;in;i) cina[i];build (1,1,n);while (m--) {int q,l,r,d;cinq;if (q1) {cinlrd; update (l,r,1,1,n,d);}else {cinlr;coutquery (l,r,1,1,n)\n;}}}虽然说线段树才是这类题的正解但是线段树代码量很大难以实现。树状数组相较于它的优点就是代码量少。但是有些问题当然我还没遇到只能用线段树来解决树状数组就显得力不从心了。
树状数组基础练习题
逆序对
来源洛谷 这是一道利用离散化结合树状数组的例题 一道逆序对的例题这个例题可以用归并排序的方法写也可以用树状数组的方法写如果要用到树状数组来写的话就要用到离散化因为数据比较大。这里我们用到的方法是树状数组。 其中的核心思想就是把数字看成树状数组的下标
#include bits/stdc.h
#define lowbit(x) (x(-x))
using namespace std;
const int N 1e65;
int a[N];
int chafen[N];
int tree[N];
int n,m;struct jiegou {int x,y;
}b[N];bool cmp (jiegou qwe,jiegou asd) {if (qwe.x!asd.x) return qwe.xasd.x;return qwe.yasd.y;
}//两个基础函数void solve () {cinn;for (int i1;in;i) {cinb[i].x;b[i].yi;}sort (b1,b1n,cmp);for (int i1;in;i) a[i]b[i].y;int res0;for (int in;i1;i--) {update(a[i],1);ressum(a[i]-1);}coutres;hreturn ;
}
动态求连续区间和
来源ACwing 模板题直接套用模板就可以
const int N 2e55;
int a[N],tree[N];int n,k;
//两个基础函数这里省略没写
void solve () {cinnk;for (int i1;in;i) {cina[i];update (i,a[i]);}for (int i1;ik;i) {int q,x,y;cinqxy;if (q1) {update (x,y);}else {coutquery (y)-query (x-1)\n;}}return;
}数星星
来源ACwing 画出图像就能发现我们只用求前面有多少小于x的数即可。前面有多少个数字那么这个输入就是几级星星。多次求前缀和优先想到我们的树状数组。我们用一个ans数组来存放i级星星有多少个。后续直接输出就可以
//两个基础函数没有写出
void solve () {int n;cinn;for (int i1;in;i) {int x,y;cinxy;x;//这里注意下标加1因为树状数组下标不为0ans[query (x)];//求x前面有多少个数字再用ans数组存起来update (x,1);}for (int i0;in;i) coutans[i]\n;return;
}
校门外的树
来源ACwing 每一个 [ l , r ] [l,r] [l,r]里面的树都是一种给出很多组lr。问当查询[l,r]时有多少种树。 其实这一题用到了一个括号序列的思想我们把 [ l , r ] [l,r] [l,r]中l上放置一个左括号r上放置一个右括号。在这一个括号里面树都是一种。这样我们只用维护括号的数量最后查询括号的数量即可。 怎么查询 [ l , r ] [l,r] [l,r]里面有多少种树我们画图就能发现。我们把r之前的左括号减去i之前的右括号即可。 故用两个树状数组分别维护左右括号的前缀和更新时记录左右括号数查询时相减即能得到结果
void solve () {int n,k;cinnk;for (int i1;ik;i) {int q,x,y;cinqxy;if (q1) {update1 (x,1);update2 (y,1);}else {coutquery1 (y) - query2 (x-1) \n;}}
}巧妙的将求树的种类转化成求括号的数量
简单题
来源ACwing 和上一题差不多但这一题是反转0,1序列。我们依然用括号的思想 [ l , r ] [l,r] [l,r]里反转我们就在两边加括号单点查询的时候我们就查询这个点被多少个括号扩了起来就反转了几下然后只能是0,1的缘故我们直接判断奇偶就行了。 多点修改单点查询十分符合树状数组直接开写。 实际上就是找这一点包括这一点之前左括号与右括号的差值
void solve () {int n,k;cinnk;for (int i1;ik;i) {int q,x,y;cinq;if (q1) {cinxy;update1 (x,1);update2 (y,1);}else {cinx;int q query1 (x) - query1 (x-1);
// int w query2 (x) - query2 (x-1); int pos query1 (x-1) - query2 (x-1);pos q;if (pos%20) cout0\n;else cout1\n;}}
}打鼹鼠
来源ACwing 这是一道二维树状数组的练习题也是属于的一道板子题可以看一看就是将一维改成二维。
const int N1040;
int c[N][N], n;void update (int x, int y, int k) {for(int ix; iN; ilowbit(i)){for(int jy; jN; jlowbit(j)){c[i][j] k;}}
}int query (int x, int y){int ans 0;for(int ix; i1; i-lowbit(i))for(int jy; j1; j-lowbit(j))ans c[i][j];return ans;
}void solve () {cinn;int xx, yy, x, y, k, op;while(cinop, op!3) {if(op1){cinxyk;update(x1, y1, k);}else{cinxyxxyy;xx, yy;coutquery (xx,yy)-query (xx,y)-query (x,yy)query (x,y)\n;}}
}
