树状数组、线段树模版
索引: (一)树状数组: a代表原始数组,c代表树状数组,n很重要!!!! (1)在多种情况下,树状数组要初始化:void init(); (2)求最低位:int lowbit(int x); (3)单点更新:void update(int x,int y); (4)前x项求和:int getsum(int x); (二)线段树 a代表原始数组,segtree代表线段树结构体 (1)建线段树,相当于初始化:void build(int l,int r,int rt); (2)单点更新:void update(int L,int C,int l,int r,int rt); (3)区间求和:int query(int L,int R,int l,int r,int rt); (4)下推 :void pushdown(int rt,int ln,int rn); //用于区间更新 (5)区间更新:void qujian_update(int L,int R,int C,int l,int r,int rt); (6)区间更新的区间查询:void qujian_update(int L,int R,int C,int l,int r,int rt);
树状数组: #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> using namespace std; typedef long long ll; int a[50005]; //原数组 int c[50005]; //树状数组 void init() //初始化a,c数组 { memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); } int n; //一共多少个兵营 int lowbit(int x) { return x&(-x); } void updata(int i,int k) //在i位置加上k,并更新数组的数据 { while(i<=n) { c[i]+=k; i+=lowbit(i); } } int getsum(int i) //求前i项的和 { int ans=0; while(i>0) { ans+=c[i]; i-=lowbit(i); } return ans; } 线段树: #include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <queue> #include <map> using namespace std; const int maxn = 50005; int T,n; int a[maxn]; string s; struct sss { int val,lazy; }SegTree[maxn<<2]; void build(int l,int r,int rt) { SegTree[rt].lazy = 0; if(l==r) { SegTree[rt].val = a[l]; return; } int mid = (l+r)/2; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val; //回溯方法 } void update(int L,int C,int l,int r,int rt) { if(l==r) { SegTree[rt].val += C; //这里是rt的val+=C,不是l或r的 return; } int mid = (l+r) >> 1 ; if(L <= mid) update(L, C, l, mid, rt<<1); else update(L, C, mid+1, r, rt<<1|1); SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val; } void pushdown(int rt,int ln,int rn) { if(SegTree[rt].lazy) { SegTree[rt<<1].lazy += SegTree[rt].lazy; SegTree[rt<<1|1].lazy += SegTree[rt].lazy; SegTree[rt<<1].val += SegTree[rt].lazy * ln; SegTree[rt<<1|1].val += SegTree[rt].lazy *rn; SegTree[rt].lazy = 0; } } void qujian_update(int L,int R,int C,int l,int r,int rt) { if(l>=L && r<=R) //只有[l,r]全部在[L,R]区间内才可以更新,直到是叶子节点 { SegTree[rt].val += C * (r-l+1); SegTree[rt].lazy += C; return; } int mid = (l+r) >> 1; pushdown(rt,mid-l+1,r-mid); if(L<=mid) qujian_update(L, R, C, l, mid, rt<<1); if(R>mid) qujian_update(L, R, C, mid+1 ,r, rt<<1|1); SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val; } int query(int L,int R,int l,int r,int rt) { if(l>=L && r<=R) return SegTree[rt].val; if(l>R || r<L) return 0; int mid = (l+r)>>1; return query(L, R, l, mid, rt<<1) + query(L, R, mid+1, r, rt<<1|1); } int qujian_query(int L,int R,int l,int r,int rt) { if(l>=L && r<=R) return SegTree[rt].val; if(l>R || r<L) return 0; int mid = (l+r)>>1; pushdown(rt, mid-l+1, r-mid); return qujian_query(L, R, l, mid, rt<<1) + qujian_query(L, R, mid+1, r, rt<<1|1); } int main() { scanf("%d",&T); for (int I=1;I<=T;I++) { cout << "Case " << I << ":" << endl; scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); } build(1, n, 1); //相当于初始化,不用像树状数组单独初始化了 while(cin >> s) { int x,y; if(s=="End") break; else { scanf("%d %d",&x,&y); if(s=="Add") update(x, y, 1, n, 1); if(s=="Sub") update(x, -y, 1, n, 1); if(s=="Query") cout << query(x, y, 1, n, 1) << endl; } } } return 0; }
模版专项 文章被收录于专栏
模版