hdu1166
裸的线段树问题,就是一个简单的单点操作和求和操作
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXN = 5e5 + 7; ll pre[MAXN], tree[MAXN * 4], ans[MAXN]; string Ins[] = {"Add", "Sub", "Query", "End"}; void Buildtree(ll p, ll l, ll r) //建树 { if (l == r) { tree[p] = pre[l]; return; } ll mid = (l + r) / 2; Buildtree(p * 2, l, mid); Buildtree(p * 2 + 1, mid + 1, r); tree[p] = tree[p * 2] + tree[p * 2 + 1]; } ll Query(ll p, ll l, ll r, ll x, ll y) //求区间和 { if (x <= l && r <= y) return tree[p]; ll mid = (l + r) / 2; if (y <= mid) return Query(p * 2, l, mid, x, y); if (x > mid) return Query(p * 2 + 1, mid + 1, r, x, y); return (Query(p * 2, l, mid, x, mid) + Query(p * 2 + 1, mid + 1, r, mid + 1, y)); } void Add(ll p, ll l, ll r, ll x, ll y) //单点操作 { if (l == r) { tree[p] += y; return; } ll mid = (l + r) / 2; if (x <= mid) Add(p * 2, l, mid, x, y); else Add(p * 2 + 1, mid + 1, r, x, y); tree[p] = tree[p * 2] + tree[p * 2 + 1]; } int main(void) { ll T; ll k = 0; scanf("%d",&T); while (T--) { ll n; memset(tree, 0, sizeof(tree)); memset(ans, 0, sizeof(ans)); memset(pre, 0, sizeof(pre)); scanf("%lld", &n); for (ll i = 1; i <= n; i++) scanf("%lld", &pre[i]); k++; printf("Case %lld:\n", k); Buildtree(1, 1, n); string s; while (cin >> s && s != Ins[3]) { ll i, j; scanf("%lld%lld", &i, &j); if (s == Ins[0]) Add(1, 1, n, i, j); if (s == Ins[1]) Add(1, 1, n, i, -j); if (s == Ins[2]) printf("%lld\n", Query(1, 1, n, i, j)); } } return 0; }
poj3468 简单区间求和
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e5+10; ll sum[MAXN<<2],add[MAXN<<2]; void push_up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void push_down(int rt,int m){ if(add[rt]){ add[rt<<1]+=add[rt]; add[rt<<1|1]+=add[rt]; sum[rt<<1]+=(m-(m>>1))*add[rt]; sum[rt<<1|1]+=(m>>1)*add[rt]; add[rt]=0; } } #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 void build(int l,int r,int rt){ add[rt]=0; if(l==r){ scanf("%lld",&sum[rt]); return ; } int mid=(l+r)>>1; build(lson); build(rson); push_up(rt); } void updata(int a,int b,ll c,int l,int r,int rt){ if(a<=l&&b>=r){ sum[rt]+=(r-l+1)*c; add[rt]+=c; return ; } push_down(rt,r-l+1); int mid=(l+r)>>1; if(a<=mid) updata(a,b,c,lson); if(b>mid) updata(a,b,c,rson); push_up(rt); } ll query(int a,int b,int l,int r,int rt){ if(a<=l&&b>=r) return sum[rt]; push_down(rt,r-l+1); int mid=(l+r)>>1; ll ans=0; if(a<=mid) ans+=query(a,b,lson); if(b>mid) ans+=query(a,b,rson); return ans; } int main(void){ int n,m; scanf("%d%d",&n,&m); build(1,n,1); while(m--){ char str[2]; int a,b; ll c; scanf("%s",str); if(str[0]=='C'){ scanf("%d%d%lld",&a,&b,&c); updata(a,b,c,1,n,1); } else{ scanf("%d%d",&a,&b); printf("%lld\n",query(a,b,1,n,1)); } } return 0; }
hdu1698 区间修改
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e5+10; ll sum[MAXN<<2],add[MAXN<<2]; void push_up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void push_down(int rt,int m){ if(add[rt]){ add[rt<<1]=add[rt]; add[rt<<1|1]=add[rt]; sum[rt<<1]=(m-(m>>1))*add[rt]; sum[rt<<1|1]=(m>>1)*add[rt]; add[rt]=0; } } #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 void build(int l,int r,int rt){ add[rt]=0; if(l==r){ sum[rt]=1; return ; } int mid=(l+r)>>1; build(lson); build(rson); push_up(rt); } void updata(int a,int b,int c,int l,int r,int rt){ if(a<=l&&b>=r){ sum[rt]=(r-l+1)*c; add[rt]=c; return ; } push_down(rt,r-l+1); int mid=(l+r)>>1; if(a<=mid) updata(a,b,c,lson); if(b>mid) updata(a,b,c,rson); push_up(rt); } ll query(int a,int b,int l,int r,int rt){ if(a<=l&&b>=r) return sum[rt]; push_down(rt,r-l+1); int mid=(l+r)>>1; ll ans=0; if(a<=mid) ans+=query(a,b,lson); if(b>mid) ans+=query(a,b,rson); return ans; } int main(void){ int n; while(cin>>n){ int i=0; while(n--){ int len,m; scanf("%d%d",&len,&m); build(1,len,1); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); updata(a,b,c,1,len,1); } printf("Case %d: The total value of the hook is %lld.\n",++i,query(1,len,1,len,1)); } } return 0; }