선분 트 리 + 나무 모양 배열 [소 담]

선분 수 와 나무 모양 의 배열 은 다음 과 같은 것 을 배 웠 습 니 다. 그것 도 몇 달 전에 배 웠 습 니 다. 이 는 그 동안 데이터 구조 가 조금도 발전 하지 않 았 다 는 것 을 설명 합 니 다. 먼저 기록 하 는 것 이 좋 겠 습 니 다. 이산 화 에 대해 서 는 현재 문제 가 비교적 적 고 먼저 쓰 지 않 겠 습 니 다.구간 조작, 스캐닝 라인 도 배 워 야 하 는데....................................................... 
문제 1: N 개의 수 와 M 번 의 조작 을 드 리 겠 습 니 다. 조작 은 두 가지 로 나 눌 수 있 습 니 다.
1, U a b 제 a 개수 증가 b;2，S a b  구간 [a, b] 의 합 을 구하 다.
이러한 문제 의 트 리 배열 은 매우 간결 하 게 실현 할 수 있다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100000+10
using namespace std;
int sum[MAXN<<1];
int N, M;
int lowbit(int x)
{
    return x & (-x);
}
void update(int x, int d)
{
    while(x <= N)
    {
        sum[x] += d;
        x += lowbit(x);
    }
}
int query(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += sum[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{
    while(scanf("%d%d", &N, &M) != EOF)
    {
        memset(sum , 0, sizeof(sum));
        int a, b;
        char op[10];
        for(int i = 1; i <= N; i++)
        {
            scanf("%d", &a);
            update(i, a);
        }
        while(M--)
        {
            scanf("%s%d%d", op, &a, &b);
            if(op[0] == 'U')
                update(a, b);
            else
                printf("%d
", query(b) - query(a-1));
        }
    }
    return 0;
}

문제 2: N 개 수 와 M 차 조작 을 드 리 겠 습 니 다. 조작 은 세 가지 로 나 눌 수 있 습 니 다.
1, U a b 의 첫 번 째 숫자 는 b 가 됩 니 다.2, S a b 구간 [a, b] 의 합;3, M a b 구간 [a, b] 의 최대 값 구하 기 
선분 트 리 구현:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100000+10
using namespace std;
int sum[MAXN<<2];
int Max[MAXN<<2];
void PushUp(int o)
{
    sum[o] = sum[o<<1] + sum[o<<1|1];
    Max[o] = max(Max[o<<1], Max[o<<1|1]);
}
void build(int o, int l, int r)
{
    if(l == r)
    {
        scanf("%d", &sum[o]);
        Max[o] = sum[o];
        return ;
    }
    int mid = (l + r) >> 1;
    build(o<<1, l, mid);
    build(o<<1|1, mid+1, r);
    PushUp(o);
}
void update(int o, int l, int r, int pos, int val)
{
    if(l == r)
    {
        Max[o] = sum[o] = val;//         val 
        return ;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid)
        update(o<<1, l, mid, pos, val);
    else
        update(o<<1|1, mid+1, r, pos, val);
    PushUp(o);
}
int querysum(int o, int l, int r, int L, int R)
{
    if(L <= l && R >= r)
        return sum[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(R <= mid)
        ans += querysum(o<<1, l, mid, L, R);
    else if(L > mid)
        ans += querysum(o<<1|1, mid+1, r, L, R);
    else
    {
        ans += querysum(o<<1, l, mid, L, mid);
        ans += querysum(o<<1|1, mid+1, r, mid+1, R);
    }
    return ans;
}
int querymax(int o, int l, int r, int L, int R)
{
    if(L <= l && R >= r)
        return Max[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(R <= mid)
        ans = max(querymax(o<<1, l, mid, L, R), ans);
    else if(L > mid)
        ans = max(querymax(o<<1|1, mid+1, r, L, R), ans);
    else
    {
        ans = max(querymax(o<<1, l, mid, L, mid), ans);
        ans = max(querymax(o<<1|1, mid+1, r, mid+1, R), ans);
    }
    return ans;
}
int main()
{
    int N, M;
    while(scanf("%d%d", &N, &M) != EOF)
    {
        build(1, 1, N);
        int a, b;
        char op[10];
        while(M--)
        {
            scanf("%s%d%d", op, &a, &b);
            if(op[0] == 'U')
                update(1, 1, N, a, b);
            else if(op[0] == 'S')
                printf("%d
", querysum(1, 1, N, a, b));
            else
                printf("%d
", querymax(1, 1, N, a, b));
        }
    }
    return 0;
}

문제 3: N 개의 수 와 M 번 의 조작 을 드 리 겠 습 니 다. 조작 은 두 가지 가 있 습 니 다.
1，A a. b c 구간 [a, b] 의 모든 수 를 c 로 변경 합 니 다.2, Q a b 구간 [a, b] 의 모든 수의 합 을 구한다.

#include <cstdio>
#define MAX 100000+10
int col[MAX<<2];
int sum[MAX<<2];
void PushUp(int o)
{
    sum[o] = sum[o<<1] + sum[o<<1|1];
}
void PushDown(int o, int m)
{
    if(col[o])
    {
        col[o<<1] = col[o<<1|1] = col[o];
        sum[o<<1] = (m - (m >> 1)) * col[o];
        sum[o<<1|1] = (m >> 1) * col[o];
        col[o] = 0;
    }
}
void build(int o, int l, int r)//  
{
    col[o] = 0;
    if(l == r)
    {
        scanf("%d",&sum[o]);
        return ;
    }
    int mid = (l + r) >> 1;
    build(o<<1,l, mid);
    build(o<<1|1, mid+1, r);
    PushUp(o);
}
void update(int o, int l, int r, int L, int R, int v)//  
{
    if(L <= l && r <= R)
    {
        col[o] = v;
        sum[o] = v * (r - l + 1);
        return ;
    }
    PushDown(o , r - l + 1);
    int mid = (l + r) >> 1;
    if (L <= mid) update(o<<1, l, mid, L , R , v);
    if (R > mid) update(o<<1|1, mid+1, r, L , R , v);
    PushUp(o);
}
int query(int o, int l, int r, int L, int R) //  
{
    if(L <= l && R >= r)
    {
        return sum[o];
    }
    PushDown(o, r-l+1);
    int mid = (r+l) >> 1;
    int res = 0;
    if(L <= mid)
    res += query(o<<1, l, mid, L, R);
    if(R > mid)
    res += query(o<<1|1, mid+1 , r, L, R);
    return res;
}
int main()
{
    int N, M;
    int a, b, v;
    char op;
    while(scanf("%d%d", &N, &M)!=EOF)
    {
        build(1, 1, N);
        while(M--)
        {
            getchar();
            scanf("%c", &op);
            if(op == 'A')
            {
                scanf("%d%d%d", &a, &b, &v);//   [a,b]       v
                update(1, 1, N, a, b, v);
            }
            else if(op == 'Q')
            {
                scanf("%d%d", &a, &b);//   [a,b]     
                printf("%d
", query(1, 1, N, a, b));
            }
        }
    }
    return 0;
}

문제 4: N 개의 수 와 M 번 의 조작 을 드 리 겠 습 니 다. 조작 은 두 가지 로 나 눌 수 있 습 니 다.
1, C a b c 는 구간 [a, b] 의 모든 수 를 c 로 추가 합 니 다.2, Q a b 구간 [a, b] 의 모든 수의 합 을 구한다.

#include<cstdio>
#include<cstring>
#define MAX 100000+10
using namespace std;
int sum[MAX<<2];
int add[MAX<<2];
void PushUp(int o)
{
    sum[o] = sum[o<<1] + sum[o<<1|1];
}
void PushDown(int o, int m)
{
    if(add[o])
    {
        add[o<<1]   += add[o];
        add[o<<1|1] += add[o];
        sum[o<<1]   += add[o] * (m-(m>>1));
        sum[o<<1|1] += add[o] * (m>>1);
        add[o] = 0;
    }
}
void build(int o,int l,int r)//  
{
    add[o] = 0;
    if(l == r)
    {
        scanf("%d",&sum[o]);
        return ;
    }
    int mid = (r+l) >> 1;
    build(o<<1, l, mid);
    build(o<<1|1, mid+1, r);
    PushUp(o);
}
void update(int o, int l, int r, int L, int R, int v)//  
{
    if(L <= l && R >= r)
    {
        add[o] += v;
        sum[o] += v * (r-l+1);
        return ;
    }
    PushDown(o, r-l+1);
    int mid = (r+l) >> 1;
    if(L <= mid) update(o<<1, l, mid, L, R, v);
    if(R >mid) update(o<<1|1, mid+1, r, L, R, v);
    PushUp(o);
}
int query(int o, int l, int r, int L, int R)//  
{
    if(L <= l && R >= r)
    {
        return sum[o];
    }
    PushDown(o, r-l+1);
    int mid = (r+l) >> 1;
    int res = 0;
    if(L <= mid)
    res += query(o<<1, l, mid, L, R);
    if(R >mid)
    res += query(o<<1|1, mid+1, r, L, R);
    return res;
}
int main()
{
    int N, M;
    int a, b, v;
    char op;
    while(scanf("%d%d", &N, &M), N||M)
    {
        build(1, 1, N);
        while(M--)
        {
            getchar();
            scanf("%c", &op);
            if(op == 'C')//  [a,b]      v
            {
                scanf("%d%d%d", &a, &b, &v);
                update(1, 1, N, a, b, v);
            }
            else if(op == 'Q')//  [a,b]     
            {
                scanf("%d%d", &a, &b);
                printf("%d
", query(1, 1, N, a, b));
            }
        }
    }
    return 0;
}