线段树专题

集训队

A 敌兵布阵

标准的线段树，套个简单模板即可，涉及单点更新，区间查询部分

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
const int maxn = 50000+5;
using namespace std;
struct {
    int left, right;
    int sum;
}tree[maxn * 4];
int n, a[maxn], p;
string judstr;
void push_up(int o)
{
    tree[o].sum = tree[2 * o].sum + tree[2 * o + 1].sum;
}
void build(int l, int r, int o)
{
    tree[o].left = l, tree[o].right = r, tree[o].sum = 0;
    if (l == r) tree[o].sum = a[l];
    else
    {
        int mid = (r + l) / 2;
        build(l, mid, 2 * o);
        build(mid + 1, r, 2 * o + 1);
        push_up(o);
    }
}
int query(int ql, int qr, int o)
{
    int l = tree[o].left, r = tree[o].right;
    if (ql <= l&&r <= qr) return tree[o].sum;
    else {
        int ans = 0;
        int mid=(l + r) / 2;
        if (ql <= mid) ans += query(ql, qr, 2 * o);
        if (qr>mid) ans += query(ql, qr, 2 * o + 1);
        return ans;
    }
}
void update(int pos, int o, int x)
{
    int l = tree[o].left,r = tree[o].right;
    if (l == r&&tree[o].left == pos)
    {
        tree[o].sum += x;
        return;
    }
    else {
        int mid = (l + r) / 2;
        if (mid<pos)
            update(pos, 2 * o + 1, x);
        else
            update(pos, 2 * o, x);
        push_up(o);
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        build(1, n, 1);
        printf("Case %d:\n", ++p);
        while (1)
        {
            int i, j;
            cin >> judstr;
            if (judstr == "End") break;
            scanf("%d%d", &i, &j);
            if (judstr == "Query")
                printf("%d\n", query(i, j, 1));
            else if (judstr == "Add")
            {
                update(i, 1, j);
            }
            else
                update(i, 1, -j);
        }
    }
    return 0;
}

B - Color the ball

线段树区间更新与查询,初始化化序列为0,更新+1

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1000000], n;
struct
{
    int l, r;
    int n;
}tree[1000000];
void build(int l, int r, int o)
{
    tree[o].l = l;
    tree[o].r = r;
    tree[o].n = 0;
    if (l != r)
    {
        int mid = (l + r) >> 1;
        build(l, mid, 2 * o);
        build(mid + 1, r, 2 * o + 1);
    }
}
void query(int o)
{
    int i;
    for (i = tree[o].l; i <= tree[o].r; i++)
        a[i] += tree[o].n;
    if (tree[o].l == tree[o].r)
        return;
    query(2 * o);
    query(2 * o + 1);
}
void update(int x, int y, int o)
{
    int l = tree[o].l, r = tree[o].r;
    if (l == x&&r == y) 
        tree[o].n++;
    else
    {
        int mid = (l + r)/2;
        if (y <= mid) update(x, y, 2 * o);
        else if (x > mid) update(x, y, 2 * o + 1);
        else
        {
            update(x, mid, 2 * o);
            update(mid+1, y, 2 * o + 1);
        }
    }
}
int main()
{
    int i, j;
    while (~scanf("%d", &n),n)
    {
        memset(a, 0, sizeof(a));
        build(1, n, 1);
        for(int p=1;p<=n;++p)
        {
            scanf("%d%d", &i, &j);
            update(i,j,1);
        }
        query(1);
        printf("%d", a[1]);
        for (int k = 2; k <= n; ++k)
            printf(" %d", a[k]);
        printf("\n");
    }
    return 0;
}

E - A Simple Problem with Integers (poj3468)

区间统一更新加c，区间查询

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int maxn = 1e5 + 5;
int n, q;
int a[maxn];
using namespace std;
typedef long long SgTreeDataType;
struct 
{
    int L, R;
    SgTreeDataType sum, lazy;
    void updata(SgTreeDataType v)
    {
        sum += (R - L + 1)*v;
        lazy += v;
    }
}tree[maxn*4];
void push_down(int o)
{
    SgTreeDataType lazyval = tree[o].lazy;
    tree[2 * o].updata(lazyval); tree[2 * o + 1].updata(lazyval);
    tree[o].lazy = 0;
}
void push_up(int o)
{
    tree[o].sum = tree[2 * o].sum + tree[2 * o + 1].sum;
}
void build_tree(int L, int R, int o)
{
    tree[o].L = L, tree[o].R = R, tree[o].sum = tree[o].lazy = 0;
    if (R == L)
        tree[o].sum = a[L];
    else 
    {
        int mid = (L + R) >> 1;
        build_tree(L, mid, o * 2);
        build_tree(mid + 1, R, o * 2 + 1);
        push_up(o);
    }
}
void updata(int QL, int QR, SgTreeDataType v, int o)
{
    int L = tree[o].L, R = tree[o].R;
    if (QL <= L && R <= QR) tree[o].updata(v);
    else
    {
        push_down(o);
        int mid = (L + R) >> 1;
        if (QL <= mid) updata(QL, QR, v, o * 2);
        if (QR >  mid) updata(QL, QR, v, o * 2 + 1);
        push_up(o);
    }
}
SgTreeDataType query(int QL, int QR, int o)
{
    int L = tree[o].L, R = tree[o].R;
    if (QL <= L && R <= QR) return tree[o].sum;
    else
    {
        push_down(o);
        int mid = (L + R) >> 1;
        SgTreeDataType res = 0;
        if (QL <= mid) res += query(QL, QR, 2 * o);
        if (QR > mid) res += query(QL, QR, 2 * o + 1);
        push_up(o);
        return res;
    }
}
int main()
{
    int x, y, c;
    char ch;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    build_tree(1, n, 1);
    while (q--)
    {
        scanf(" %c", &ch);
        if (ch == 'Q') {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(x, y, 1));
        }
        else
        {
            scanf("%d%d%d", &x, &y,&c);
            updata(x, y, c, 1);
        }
    }
    return 0;
}