线段树（简单）

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;
}