超详细の树状数组讲解!

这篇具有很好参考价值的文章主要介绍了超详细の树状数组讲解!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

树状数组

以下有错误的话欢迎指正

由于篇幅问题每道题目的代码在每一板块最后折叠给出

其实线段树能维护的东西比树状数组能维护的东西多得多,但是树状数组代码好写啊!

一维树状数组

最为常用的树状数组,我们一般都是用这个来解决问题,二维的后面会讲。

引入

我们在进行数列操作的时候,经常会遇到带有区间修改的一类问题,比如给定一个数列,支持区间加单点查询,或者支持区间查询单点修改之类的。

给定一个序列,需要支持单点修改和区间加,设元素个数为 \(n\),操作次数为 \(m\),那么我们最朴素的暴力的复杂度最坏情况是 \(O(nm)\) 的,显然只要数据范围稍微大一点暴力就会挂,这个时候我们就需要用一些数据结构来进行优化,比如线段树或者我们接下来要讲的树状数组。

介绍

首先要学会树状数组,我们就要先理解一个函数:lowbit 函数。

lowbit 函数的返回值就是由当前数转为二进制后最低位的 \(1\) 与后面的零所构成的数值,比如一个二进制数 \(1010100\),他的 lowbit 值就是 \(lowbit(1010100)=100\),转为十进制也就是 \(lowbit(84)=4\)

我们如何能求出这个 lowbit 函数的值呢?

  • 暴力,每次模 \(2\),但显然复杂度为 \(O(\log x)\),由于有更快速便捷的方法,我们不能接受多一只 \(\log\) 的复杂度。

  • 我们考虑到是在二进制下,那我们就可以用快速的位运算来解决这个问题,我们先把原数如 \(1010100\) 进行取反,得到:\(0101011\),这个时候,我们再给取反后的数字加上 \(1\),这个时候,你会发现,得到的数为 \(0101100\),这个数值和一开始的数的关系,就是除了最后一位 \(1\) 和后面的 \(0\),其他位都是不同的!所以我们将这两个一 & 就得到了我们的 lowbit ,也就是 \(lowbit(x)=x\&(\sim x+1)\)

  • 我们想到计算机中对于负数的存储用的是补码,也就是如果一个数是正数,他的补码就是他本身,如果是负数,那么他的补码就是他的反码然后加一。根据这个特性,我们知道 \(-1010100\) 的反码为 \(0101011\) 那么补码就是 \(0101100\),这样再和 \(1010100\) & 一下不就也得到了 lowbit 吗,也就是 \(lowbit(x)=x\&-x\)

于是我们转化成代码就是:

inline int lowbit(int x){return x&-x;}

这个有什么用,我们后面讲到操作就知道了。

树状数组是长这个样子的:

超详细の树状数组讲解!

感谢树状数组详解 - Xenny - 博客园的图片。

其中黑色的块是原来的数组下面会用 \(a[i]\) 表示,红色的是树状数组下面会用 \(s[i]\) 来表示。

树状数组的每一个块,存放的是子节点的和。

用十进制可以不是很好结合前面的 lowbit ,所以下面的下标我用的是二进制

我们可以形象的看作每个节点 \(x\) 所存的是以当前编号 \(x\) 的节点为起点,向左 \(lowbit(x)\) 个单位的所有点的总和。

单点修改区间查询

也就是这道题目:【模板】树状数组 1 - 洛谷

我们现在来考虑如何单点修改,假设我们要修改里面的 \(3\) 号点。

我们发现,由于有一些节点是包含 \(3\) 的值的,所以我们也要更新那些值,也就是同时更新 \(3,4,8\) 号节点,我们转成二进制看一下:\(11,100,1000\)

不知道你发现了什么没有。

可以看出,下一个修改的节点的编号,就是当前的数 \(x\),与当前数的 lowbit 值的和!

所以我们对于一次修改操作,可以写出以下的代码:

inline void add(int x,int k){while(x<=n)t[x]+=k,x+=lowbit(x);}

好神奇!

然后我们再来看区间求和的操作。

我们的树状数组维护的就是前缀和,所以我们在查询的时候肯定不能一个一个遍历,举个例子,假设我们需要查询前 \(7\) 个数的和。

我们发现我们实际上需要查找的有 \(7,6,4\) 号节点。

我们再转成二进制看看:\(111,110,100\)

这次的很明显了吧!

我们发现,下一个需要修改的节点,就是当前 \(x\) 的值减去 \(lowbit(x)\),所以,我们就又可以写出以下的代码:

inline int ask(int x){int o=0;while(x>=1)o+=t[x],x-=lb(x);return o;}

对于区间查询,我们利用前缀和的思想,设需要查询的区间为 \([l,r]\),我们则可以直接输出 \(ask(r)-ask(l-1)\)

至此我们就完成了支持区间查询和单点修改的操作。

区间查询和单点修改的复杂度最坏均为 \(O(\log n)\),所以总复杂度为 \(O(m\log n)\)

完整代码:

树状数组单点修改区间查询
#include<bits/stdc++.h>
#define int long long
#define N 1001000
using namespace std;
int n,m,t[N];
inline int lb(int x){return x&-x;}
inline void add(int x,int k){while(x<=n)t[x]+=k,x+=lb(x);}
inline int sum(int x){int ans=0;while(x>=1)ans+=t[x],x-=lb(x);return ans;}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){int a;cin>>a;add(i,a);}
	for(int i=1;i<=m;i++)
	{
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)add(x,y);
		if(op==2)cout<<(sum(y)-sum(x-1))<<endl;
	}
	return 0;
}

区间修改单点查询

【模板】树状数组 2 - 洛谷

我们想一想,什么东西做区间修改最快?

那当然是差分!直接 \(O(1)\) 修改!但是有一个致命的缺点:查询第 \(x\) 个数的值的复杂度为 \(O(x)\),也就是说,最坏复杂度为 \(O(mn)\),我们怎么能接受这么高的复杂度!

那我们用树状数组维护这个差分数组不就好了?

我们单点查询变成了之前的查询前 \(x\) 个数的和,然后我们的区间修改,利用差分的思想,直接修改 \(add(l,k),add(r+1,-k)\) 就好了。

完整 code:

树状数组区间修改单点查询
#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,a[N],t[N];
inline int lb(int x){return x&-x;}
inline void add(int x,int k){while(x<=n)t[x]+=k,x+=lb(x);}
inline int ask(int x){int ans=0;while(x>=1)ans+=t[x],x-=lb(x);return ans;}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int op,x,y,k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		if(op==2)
		{
			cin>>x;
			int ans=ask(x)+a[x];
			cout<<ans<<endl;
		}
	}
	return 0;
}

区间查询区间修改

【模板】线段树 1 - 洛谷

线段树的模板的操作就是区间查询和区间修改,但线段树码量比较大,所以我们还可以用树状数组来解决。

我们如果想要完成这个操作的话,还是需要用到上面的差分的思想。

首先我们和上面一样,用差分的话,我们就可以做到 \(O(\log n)\) 的修改,但是,我们对于区间查询,似乎没有什么好办法。

我们假设要查询前 \(5\) 个数的和:

超详细の树状数组讲解!

图片来源:# 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

图中的蓝色阴影部分就是我们要求的值,用 \(S[i]\) 表示我们第 \(i\) 个数的值,\(t1[j]\) 表示当前维护的差分数组,很容易可以列出式子:

\[S[i]=\sum_{j=1}^{i}t1[j] \]

然后在把 \(1\sim x\) 的数都给加起来:

\[sum=\sum_{i=1}^{x}S[i]=\sum_{i=1}^{x}\sum_{j=1}^{i}t1[j] \]

我们发现这个式子一点也不好算,所以我们转换一下思路:

超详细の树状数组讲解!

图片来源:# 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

补全之后发现,这个总的面积,就是 \(S[x]\times x+S[x]\),最后多出来的那个是最后一行,是我们补上的。

那我们看看黄色面积怎么求:

\[\sum_{i=1}^{x}i\times t1[i] \]

这个东西好像比上面的好算一点(?

用前缀和维护一下不就更好了!

我们记 \(t2[i]\) 来维护前 \(i\)\(i\times t1[i]\) 的总和,那我们用树状数组维护一下,不就也是 \(O(\log n)\) 了吗。

我们最后用两个树状数组,来维护了两个东西达到了区间修改区间查询的目的。

对于我们的修改操作的代码,我们改成这样:

inline void add(int x,int k){int xx=x;while(x<=n)t1[x]+=k,t2[x]+=(k*xx),x+=lb(x);}

我们很容易理解,就是多了个 t2[x]+=(k*xx),因为我们说了是维护的前 \(i\times t1[i]\) 的总和,所以我们减去的时候要乘上 \(xx\),并且要一直往上把所有包含他的节点都修改一遍。

再来看我们的查询操作:

inline int ask(int x){int ans=0,xx=x;while(x>=1)ans+=(xx+1)*t1[x]-t2[x],x-=lb(x);return ans;} 

里面对于 \(t1\) 的累加应该很好理解,就是上面说的求整个矩形的面积,然后我们对于 \(t2\),我们前说了就是维护前 \(i\times t1[i]\) 的总和,那么我们这么循环下去就是减去了 \(x\times t2[x]\),然后这两个一减,也就是上面的矩形总面积减去黄色面积,那不就是我们要求的蓝色面积了吗。

值得注意的是,\(t1\) 的思想是差分,\(t2\) 的思想是前缀和,千万不要搞混。

完整代码:

树状数组区间修改区间求和
#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,a[N],t1[N],t2[N];
inline int lb(int x){return x&-x;}
inline void add(int x,int k){int xx=x;while(x<=n)t1[x]+=k,t2[x]+=(k*xx),x+=lb(x);}
inline int ask(int x){int ans=0,xx=x;while(x>=1)ans+=(xx+1)*t1[x]-t2[x],x-=lb(x);return ans;} 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)add(i,a[i]-a[i-1]);
	for(int i=1;i<=m;i++)
	{
		int op,l,r,x;
		cin>>op;
		if(op==1)
		{
			cin>>l>>r>>x;
			add(l,x);
			add(r+1,-x);
		}
		if(op==2)
		{
			cin>>l>>r;
			cout<<(ask(r)-ask(l-1))<<endl;
		}
	}
	return 0;
}

二维树状数组

树状数组比线段树更容易扩展到二维,所以我们就来研究如何把它扩到二维。

我们在之前就已经说过,一维的树状数组可以看作是一个点以自身为起点向左 lowbit 个单位的总和,那我们的二维的树状数组的一点 \((x,y)\) 是不是也可以看作是向左 \(lowbit(x)\),向上 \(lowbit(y)\) 个单位的矩形内元素的总和呢?

答案是 true。

单点修改区间查询

例题:二维树状数组单点修改区间查询

我们对于这个操作,需要掌握的前置知识就是二维的前缀和。

超详细の树状数组讲解!

图片来源:二维前缀和详解 - 没有你哪有我 - 博客园

我们可以看到利用二维前缀和的思想,假设我们要求横坐标为 \(i\sim x\),纵坐标为 \(j\sim y\) 的矩阵内元素的总和,可以得到一个公式:

\[SUM=S[x][y]-S[x][j-1]-S[i-1][y]+S[i-1][j-1] \]

因为我们维护的相当于二维前缀和,那么我们就可以根据这个同样去求解我们的二维树状数组的区间查询。

贴一下完整 code:

二维树状数组单点修改区间查询
#include<bits/stdc++.h>
#define int long long
#define N 4100
using namespace std;
int n,m,t[N][N];
inline int lb(int x){return x&-x;}
inline void add(int x,int y,int k)
{
    while(x<=n)
    {
        int j=y;
        while(j<=m)
        {
            t[x][j]+=k;
            j+=lb(j);
        }
        x+=lb(x);
    }
}
inline int ask(int x,int y)
{
    int res=0;
    while(x>=1)
    {
        int j=y;
        while(j>=1)
        {
            res+=t[x][j];
            j-=lb(j);
        }
        x-=lb(x);
    }
    return res;
}
signed main()
{
    cin>>n>>m;
    int op,a,b,c,d;
    while(cin>>op)
    {
        if(op==1)
        {
            cin>>a>>b>>c;
            add(a,b,c);
        }
        if(op==2)
        {
            int ans=0;
            cin>>a>>b>>c>>d;
            ans=ask(c,d)+ask(a-1,b-1)-ask(c,b-1)-ask(a-1,d);
            cout<<ans<<endl;
        }
    }
    return 0;
}

我们在修改的时候,就像之前的一样进行修改即可,只不过是多了一个 \(y\),就是把原来的一层循环加了一层。

在区间求和的时候,我们就可以直接跟上面二维前缀和一样直接求出来了。

单次修改或查询近似为 \(O(\log^{2}n)\),总复杂度为 \(O(m\log^{2}n)\)

单点查询区间修改

二维树状数组区间修改单点查询

我们上面用了一维树状数组的单点修改区间查询的前缀和思想,那么我们是不是也可以用一维树状数组的区间修改单点查询的差分思想来转到二维上来呢?

答案为 true。

我们还是看上面那张图:

超详细の树状数组讲解!

我们可以推出差分数组中一个点的值为:

\[S[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1] \]

其实就是根据原数组是差分数组的前缀和数组来推的。

那我们就可以和之前的差分一样,对于单点查询我们就直接求前缀和,也就是这样写:

inline int ask(int x,int y)
{
    int res=0;
    while(x>=1)
    {
        int j=y;
        while(j>=1)
        {
            res+=t[x][j];
            j-=lb(j);
        }
        x-=lb(x);
    }
    return res;
}

对的就是和上面的一摸一样,调用的时候就直接 ask(x,y) 即可查询当前下标为 \((x,y)\) 的点的值。

对于修改操作,我们从前面的前缀和公式也能得到一些灵感,我们这样写:

add(a,b,k);
add(a,d+1,-k);
add(c+1,b,-k);
add(c+1,d+1,k);

同理 add 函数的代码和上面的是一样的。

我们来看这四个操作,有没有很像是前缀和的四个矩形,只不过是换成了差分的 \(+1\)

我们还是根据上面差分数组的公式来进行修改,我们就会发现实际上就是给 \((1,1),(c,d)\) 的矩形加了 \(k\),我们由于是维护的差分数组所以要 \(+1\),然后由于我们两个加起来肯定是中间有很多地方是不需要加的,比如 \((1,1),(a,d+1)\)\((1,1),(c+1,b)\) 这两个矩形,是多加了的,我们就给他减掉 \(k\),然后你会发现 \((1,1),(a,b)\) 多减了一个 \(k\),所以我们给他加回来,由于是差分,都是单点的修改。

每一次操作的复杂度匀以下约为 \(O(\log^{2}n)\),总复杂度 \(O(m\log^{2}n)\)

完整代码:

二维树状数组区间修改单点查询
#include<bits/stdc++.h>
#define int long long
#define N 4100
using namespace std;
int n,m,t[N][N];
inline int lb(int x){return x&-x;}
inline void add(int x,int y,int k)
{
	while(x<=n)
	{
		int j=y;
		while(j<=m)
		{
			t[x][j]+=k;
			j+=lb(j);
		}
		x+=lb(x);
	}
}
inline int ask(int x,int y)
{
	int res=0;
	while(x>=1)
	{
		int j=y;
		while(j>=1)
		{
			res+=t[x][j];
			j-=lb(j);
		}
		x-=lb(x);
	}
	return res;
}
signed main()
{
	cin>>n>>m;
	int op,a,c,b,d,k;
	while(cin>>op)
	{
		if(op==1)
		{
			cin>>a>>b>>c>>d>>k;
			add(a,b,k);
			add(a,d+1,-k);
			add(c+1,b,-k);
			add(c+1,d+1,k);
		}
		if(op==2)
		{
			cin>>a>>b;
			cout<<ask(a,b)<<endl;
		}
	}
	return 0;
}

区间查询区间修改

P4514上帝造题的七分钟 - 洛谷

我们根据上面的前缀和的定义,我们不难发现对于一个二维差分数组,一个点 \((x,y)\) 的二位前缀和就是:

\[SUM=\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{h=1}^{i}\sum_{k=1}^{j}S[h][k] \]

只是看这四重循坏就知道暴力肯定是不行的,那我们怎么优化呢?

我们借鉴一下一维的区间查询区间修改的做法,对于上面的式子,我们把后两层枚举拆开看看。

我们可以发现 \(S[1][1]\) 出现了 \(x\times y\) 次,\(S[1][2]\) 出现了 \(x\times (y-1)\) 次,因为只有 \(j=1\) 的时候是没有 \(S[1][2]\)的;同理我们可以推出一个一般的形式:\(S[h][k]\) 出现了 \((x-h+1)\times (y-k+1)\) 次,也就是说我们的式子可以化成下面的样子:

\[SUM=\sum_{i=1}^{x}\sum_{j=1}^{y}S[i][j]\times (x-i+1)\times (y-j+1) \]

我们把后面的给展开一下:

\[SUM=\sum_{i=1}^{x}\sum_{j=1}^{y}S[i][j]\times (xy-xj-yi+ij-i-j+x+y+1) \]

最后我们稍微合并一下得到:

\[SUM=\sum_{i=1}^{x}\sum_{j=1}^{y}(xy+x+y+1)\times S[i][j]-j(x+1)\times S[i][j]-i(y+1)\times S[i][j]+ij\times S[i][j] \]

我们发现里面只需要维护四个东西就可以完成我们的查询操作了:\(S[i][j],S[i][j]\times i,S[i][j]\times j,S[i][j]\times i\times j\)

我们来看一下修改的代码:

inline void add(int x,int y,int k)
{
    for(int i=x;i<=n;i+=lb(i))
      for(int j=y;j<=m;j+=lb(j))
        t[i][j]+=k,ti[i][j]+=k*x,tj[i][j]+=k*y,tij[i][j]+=k*x*y;
}

我们在进行修改的时候就要对应我们每一个数组维护的值来修改,修改的时候加上的值都要乘以对应的系数,而在主函数中,我们是跟差分的一样来写四次 add 操作。

而我们的求和操作需要这样写:

inline int ask(int x,int y)
{
    int res=0;
    for(int i=x;i>=1;i-=lb(i))
      for(int j=y;j>=1;j-=lb(j))
        res+=t[i][j]*(x*y+x+y+1)-ti[i][j]*(y+1)-tj[i][j]*(x+1)+tij[i][j];
    return res;
}

这里乘起来的系数就是上面的公式推导的,对于我们已经维护好的我们就直接调用就好。

完整 code:

二维树状数组区间修改区间求和
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define N 2100
using namespace std;
int n,m,t[N][N],ti[N][N],tj[N][N],tij[N][N]; 
inline int lb(int x){return x&-x;}
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void print(int x){if(x>=10)print(x/10);putchar(x%10+48);}
inline void add(int x,int y,int k)
{
	for(int i=x;i<=n;i+=lb(i))
	  for(int j=y;j<=m;j+=lb(j))
	    t[i][j]+=k,ti[i][j]+=k*x,tj[i][j]+=k*y,tij[i][j]+=k*x*y;
}
inline int ask(int x,int y)
{
	int res=0;
	for(int i=x;i>=1;i-=lb(i))
	  for(int j=y;j>=1;j-=lb(j))
	    res+=t[i][j]*(x*y+x+y+1)-ti[i][j]*(y+1)-tj[i][j]*(x+1)+tij[i][j];
	return res;
}
signed main()
{
	char op;
	int a,b,c,d,k;
	cin>>op,n=read(),m=read();
	while(cin>>op)
	{
		if(op=='L')
		{
			a=read(),b=read(),c=read(),d=read(),k=read();
			add(a,b,k);
			add(a,d+1,-k);
			add(c+1,b,-k);
			add(c+1,d+1,k);
		}
		if(op=='k')
		{
			a=read(),b=read(),c=read(),d=read(); 
			int ans=ask(c,d)+ask(a-1,b-1);
			ans-=ask(a-1,d)+ask(c,b-1);
			cout<<ans<<endl;
		}
	}
	return 0;
}

写在最后

以前稀里糊涂的学了一遍树状数组,现在来算是重修了一下。

突然发现发明这个东西的人好厉害,尤其是对于 lowbit 的使用,很奇妙。

有没看明白的可以评论。文章来源地址https://www.toymoban.com/news/detail-468840.html

到了这里,关于超详细の树状数组讲解!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深入理解树状数组

    树状数组(BIT, Binary Indexed Tree)是简洁优美的数据结构,它能在很少的代码量下支持 单点修改 和 区间查询 ,我们先以 a[] {1, 2, 3, 4, 5, 6} 数组为例建立树状数组看一下树状数组的样子: 可以发现:不是所有节点都是连接在一起的,c[1], c[2], c[3], c[4] 和 c[5], c[6] 分别构成了两棵

    2024年02月08日
    浏览(34)
  • 树状数组笔记

    数组、前缀和、树状数组的区别:         数组:修改某点O(1),求区间O(n)         前缀和:修改某点O(n),求区间O(1)         树状数组:修改某点O(logn),求区间O(logn) 树状数组采取折中的方式,降低整体的时间复杂度。 由于算法复杂度取决于最坏的情

    2024年02月15日
    浏览(33)
  • 树状数组的扩展应用

    「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录 O(N) 建树 方法一 方法二 维护区间和 单点修改,区间查询 区间修改,单点查询 区间修改,区间查询 维护二维子矩阵和(二维树状数组) 单点修改,子矩阵查询 子矩阵修改,单点查询 子矩阵修改,子矩

    2024年02月15日
    浏览(30)
  • 树状数组

    「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录 定义 基本概念 基本原理 单点修改 分析 代码实现 区间查询 分析 代码实现 整体代码 练手题目 小结 参考资料 树状数组 是一种支持 单点修改 和 区间查询 的数据结构。 普通的树状数组 只能用来维护像

    2024年02月16日
    浏览(31)
  • 【学习笔记】树状数组

    树状数组是一种数据结构,普通树状数组维护的信息及运算要满足结合律且可差分。 树状数组是用长度为 (n) 的数组存储的。我们假设这个数组为 (n) ,令 lowbit(i)=i(-i) ,则 (c_i) 保存的是向前 lowbit(i) 长度的 (a) 数组区间和。 单点加:从 (i) 开始,修改所有包含 (a_i)

    2024年02月15日
    浏览(40)
  • 【JavaSE】多图解,保姆级详细讲解数组、二维数组--建议收藏

    🌱博主简介:是瑶瑶子啦,一名大一计科生,目前在努力学习JavaSE。热爱写博客~正在努力成为一个厉害的开发程序媛! 📜所属专栏:爪洼岛冒险记【从小白到大佬之路】 ✈往期博文回顾: 【爪洼岛冒险记】第4站 🕵️‍♂️近期目标:成为千粉小博主。 🙇‍♀️写博客理

    2024年01月16日
    浏览(42)
  • 243. 一个简单的整数问题2(树状数组)

    输入样例: 输出样例:  解析:         一般树状数组都是单点修改、区间查询或者单点查询、区间修改。这道题都是区间操作。                    1. 区间修改用数组数组维护差分数组         2. 区间查询,需要log计算两个端点的前缀和。上图右侧,可以得出,计算

    2024年02月14日
    浏览(37)
  • 《算法竞赛进阶指南》0x42 树状数组

    题意: 二维平面给定一些点,询问 v 形和 ∧ 形数目 解析: 对于 ∧ 形: ( i , y ) (i,y) ( i , y ) ,考虑左右两侧比该点低的点的个数。树状数组查询 y j y y_j y y j ​ y 的点的个数。因为总共有 y − 1 y-1 y − 1 个点比当前点低,有 n − y n-y n − y 个点比当前点高。 v型同理。 代码

    2023年04月11日
    浏览(37)
  • 【C语言】指针的基本知识详细讲解(指针数组、数组指针、函数指针....

    接着上次的函数的基本知识,今天我们来讲一讲🔍指针 目录 一、指针的概念 二、指针变量 三、野指针 四、字符指针 五、指针与数组 六、指针数组 七、数组指针  八、指针与函数 总结 一、指针的概念 1.1、变量和地址 所谓指针,也就是内存的地址;所谓指针变量,也就是

    2023年04月08日
    浏览(38)
  • 把树状数组在页面显示成‘/‘/‘形式,并搜索想要的值

    大概思路 在Vue中,若要将树状数组以类似于文件路径的形式(即“/”分隔)显示在页面上,可以按照以下步骤操作: 首先,假设您有一个树状数组,其结构可能如下所示: 接下来,在Vue组件中,您可以编写一个计算属性或方法来递归地处理这个树形结构并将其转换为包含路

    2024年01月16日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包