数据结构模板代码合集(不完整)

P3368 【模板】树状数组 2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7;int n, m, s, t;
int ans;
int a[maxn];
struct node{int l, r;int num;
}tr[maxn * 4];void build(int p, int l, int r){tr[p] = {l, r, 0};if(l == r){tr[p].num = a[l];return ;}int mid = l + r >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);
}		void modify(int p, int l, int r, int k) {if(tr[p].l >= l && tr[p].r <= r) {tr[p].num += k;return ;}int mid = tr[p].l + tr[p].r >> 1;if(l <= mid) modify(p << 1, l, r, k);if(r > mid) modify(p << 1 | 1, l, r, k);
}void query(int p, int x){	ans += tr[p].num;if(tr[p].l == tr[p].r) return;int mid = tr[p].l + tr[p].r >> 1;if(x <= mid) query(p << 1, x);else query(p << 1 | 1, x); 
}int main(){cin >> n >> m;for (int i = 1; i <= n; ++ i) {scanf("%d", &a[i]);}build(1, 1, n);for (int i = 1; i <= m; ++ i) {int c;scanf("%d", &c);if(c == 1) {int x, y, z;scanf("%d%d%d", &x, &y, &z);modify(1, x, y, z);}else {ans = 0;int x;scanf("%d", &x);query(1, x);printf("%d\n", ans);}}return 0;
}

P3374 【模板】树状数组 1

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{ll l,r,sum;
};
node tree[10000005];
int n,m,input[5000005];
void build(int i,int l,int r){tree[i].l=l;tree[i].r=r;if(l==r){tree[i].sum=input[l];return;}int mid=(l+r)>>1;build(i*2,l,mid);build(i*2+1,mid+1,r);tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
void add(int i,int dis,int k){if(tree[i].l==tree[i].r){tree[i].sum+=k;return ;}if(dis<=tree[i*2].r)  add(i*2,dis,k);else add(i*2+1,dis,k);tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;return ;
}
int search(int i,int l,int r){if(tree[i].l>=l && tree[i].r<=r)return tree[i].sum;if(tree[i].r<l || tree[i].l>r)  return 0;int s=0;if(tree[i*2].r>=l)  s+=search(i*2,l,r);if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);return s;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>input[i];build(1,1,n);//cin>>m;while(m--){int op;cin>>op;if(op==1){int x,y,z;cin>>x>>z;//input[x]^=z;add(1,x,z);}else{;int x,y;cin>>x>>y;cout<<search(1,x,y)<<endl;}} return 0;
} 

P3372 【模板】线段树 1

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
struct node{int l,r,sum,lz;
}tree[N*4];
int n,q,a[N];
void build(int p,int l,int r){tree[p].l=l,tree[p].r=r;if(l==r){tree[p].sum=a[l];return;}int mid=(l+r)>>1;build(p*2,l,mid);build(p*2+1,mid+1,r);tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void pushdown(int p){if(tree[p].lz){int mid=(tree[p].l+tree[p].r)>>1;tree[p*2].lz+=tree[p].lz;tree[p*2+1].lz+=tree[p].lz;tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].lz;tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].lz;tree[p].lz=0;}
}
void add(int p,int l,int r,int k){if(tree[p].r<l||tree[p].l>r) return;if(tree[p].l>=l&&tree[p].r<=r){tree[p].sum+=(tree[p].r-tree[p].l+1)*k;tree[p].lz+=k;return;}pushdown(p);if(tree[p*2].r>=l) add(p*2,l,r,k);if(tree[p*2+1].l<=r) add(p*2+1,l,r,k);tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
int search(int p,int l,int r){if(tree[p].r<l||tree[p].l>r) return 0;if(tree[p].l>=l&&tree[p].r<=r) return tree[p].sum;pushdown(p);int s=0;if(tree[p*2].r>=l) s+=search(p*2,l,r);if(tree[p*2+1].l<=r) s+=search(p*2+1,l,r);return s;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie();cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(q--){int op,l,r,x;cin>>op;if(op==1){cin>>l>>r>>x;add(1,l,r,x);}else{cin>>l>>r;cout<<search(1,l,r)<<endl;}}return 0;
}