首页 > 其他分享 >从零开始的树状数组

从零开始的树状数组

时间:2023-03-27 12:25:24浏览次数:57  
标签:10 CH 树状 int 从零开始 数组 cs FL define

P3374 【模板】树状数组 1

点击查看代码
#include<bits/stdc++.h>
#define cs const
#define il inline
#define pc(i) putchar(i)
#define LL long long
#define fi first
#define se second
#define pub push_back
#define rdm(a,b) ((a)+srd()%((b)-(a)+1))
#define fo(i,j,k) for(int i=(j);(i)<=(k);++(i))
#define of(i,j,k) for(int i=(j);(i)>=(k);--(i))
#define pii pair<int,int>
#define debug printf("now is Line %d.\n",__LINE__);
using namespace std;
mt19937 srd(time(0));
cs int inf=1e9+7,Mod=998244353,N=5e5+7;
int FL,CH;
template<typename T> bool in(T&a)
{
    for(FL=1;!isdigit(CH)&&CH!=EOF;CH=getchar())
        if(CH=='-')FL=-1;
    for(a=0;isdigit(CH);CH=getchar())
        a=a*10+CH-'0';
    return a*=FL,CH==EOF?0:1;
}
template<typename T,typename...Args>
int in(T&a,Args&...args){return in(a)+in(args...);}
void wt(int x){if(x<0)x=-x,pc('-');if(x>9)wt(x/10);pc(x%10|48);}
int n,m,a[N];
namespace Bit
{
	#define lowbit(x) (x&-x)
	int t[N];
	il int add(int x,cs int k){ for(;x<=n;x+=lowbit(x)) t[x]+=k; }
	il int query(int x){ int r=0;for(;x;x-=lowbit(x)) r+=t[x];return r; }
	#undef lowbit(x)
}
signed main()
{
	in(n,m); fo(i,1,n) in(a[i]),Bit::add(i,a[i]);
	while(m--) 
	{ 
		int op,x,y; in(op,x,y);
		if(op==1) Bit::add(x,y);
		else wt(Bit::query(y)-Bit::query(x-1)),pc('\n');
	}
    return 0;
}

P3368 【模板】树状数组 2

点击查看代码
#include<bits/stdc++.h>
#define cs const
#define il inline
#define pc(i) putchar(i)
#define LL long long
#define fi first
#define se second
#define pub push_back
#define rdm(a,b) ((a)+srd()%((b)-(a)+1))
#define fo(i,j,k) for(int i=(j);(i)<=(k);++(i))
#define of(i,j,k) for(int i=(j);(i)>=(k);--(i))
#define pii pair<int,int>
#define debug printf("now is Line %d.\n",__LINE__);
using namespace std;
mt19937 srd(time(0));
cs int inf=1e9+7,Mod=998244353,N=5e5+7;
int FL,CH;
template<typename T> bool in(T&a)
{
    for(FL=1;!isdigit(CH)&&CH!=EOF;CH=getchar())
        if(CH=='-')FL=-1;
    for(a=0;isdigit(CH);CH=getchar())
        a=a*10+CH-'0';
    return a*=FL,CH==EOF?0:1;
}
template<typename T,typename...Args>
int in(T&a,Args&...args){return in(a)+in(args...);}
void wt(int x){if(x<0)x=-x,pc('-');if(x>9)wt(x/10);pc(x%10|48);}
int n,m,a[N],s[N];
namespace Bit
{
	#define lowbit(x) (x&-x)
	int t[N];
	il int add(int x,cs int k){ for(;x<=n;x+=lowbit(x)) t[x]+=k; }
	il int query(int x){ int r=0;for(;x;x-=lowbit(x)) r+=t[x];return r; }
	#undef lowbit(x)
}
signed main()
{
	in(n,m); fo(i,1,n) in(a[i]),s[i]=a[i]-a[i-1],Bit::add(i,s[i]);
	while(m--) 
	{ 
		int op,x,y,k; in(op);
		if(op==1) in(x,y,k),Bit::add(x,k),Bit::add(y+1,-k);
		else in(x),wt(Bit::query(x)),pc('\n');
	}
    return 0;
}

标签:10,CH,树状,int,从零开始,数组,cs,FL,define
From: https://www.cnblogs.com/Bertidurlah/p/17261112.html

相关文章