首页 > 代码库 > 樹狀數組區間操作模板
樹狀數組區間操作模板
樹狀數組支持區間修改與區間查詢，很久沒編，又快忘了，編程時要注意的兩點是：1、樹狀數組前綴和可能會爆int 2、用%d讀入long long即使輸入數據保證小於10^9也可能出問題
記錄差分數組a[i]=num[i]-num[i-1];
sum[i]=sum[1]+sum[2]+...+sum[n]
=a1+a1+a2+a1+a2+a3+...+a1+a2+...+an
=n*a1+(n-1)*a2+...+1*an
=(n+1)*(a1+a2+...+an)-1*a1-2*a2-...-(n)*an
分別處理segma(ai)和segma(ai*i)
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 110000#define MAXV MAXN*2#define MAXE MAXV*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;inline int nextInt(){ char ch; int x=0; bool flag=false; do ch=getchar(),flag=(ch==‘-‘)?true:flag; while(ch<‘0‘||ch>‘9‘); do x=x*10+ch-‘0‘; while (ch=getchar(),ch<=‘9‘ && ch>=‘0‘); return x*(flag?-1:1);}int n,m;struct Edge{ int np; Edge *next;}E[MAXE],*V[MAXV];int tope=-1;void addedge(int x,int y){ E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope];}struct aaa{ int val,id;};bool operator <(aaa a1,aaa a2){ return a1.val<a2.val;}multiset<aaa>S;int ptr[MAXN][2];int num[MAXN];int gp[MAXN];bool vis[MAXN];bool vis2[MAXN];bool dfs(int now,int g){ if (now==-1)return true; if (vis2[now]) { return gp[now]==g; } gp[now]=g; if (ptr[now][g]==-1)return false; vis[now]=vis2[now]=true; bool t=dfs(ptr[now][1-g],g) && dfs(ptr[now][g],g); vis2[now]=false; return t;}int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int i,j,k; int x,y,z; int a,b; scanf("%d%d%d",&n,&a,&b); aaa at; for (i=0;i<n;i++) { scanf("%d",&x); num[i]=x; at.val=x; at.id=i; S.insert(at); } multiset<aaa>::iterator it1; memset(ptr,-1,sizeof(ptr)); for (i=0;i<n;i++) { at.val=a-num[i]; it1=S.find(at); if (it1!=S.end()) { ptr[i][0]=it1->id; } at.val=b-num[i]; it1=S.find(at); if (it1!=S.end()) { ptr[i][1]=it1->id; } } for (i=0;i<n;i++) { if (vis[i])continue; if (!dfs(i,0)) { if (!dfs(i,1)) { printf("NO\n"); return 0; } } } printf("YES\n"); for (i=0;i<n;i++) { printf("%d ",gp[i]); } return 0;}
樹狀數組區間操作模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。