[주제] 선분 수 & & 나무 모양 배열

복습 이 라 고 할 까..
간단히 말씀 드 리 겠 습 니 다.둘 다 구간 조작 을 한다.먼저 트 리 배열: 트 리 배열 은 접두사 와 최적화 에 해당 하기 때문에 구간 감법 에 만족 하지 않 는 것 은 유지 할 수 없습니다 (예 를 들 어 RMQ). 그래서 보통 트 리 배열 로 구간 과 유지 합 니 다.그러나 트 리 배열 은 보통 [구간 수정 점 조회] 나 [점 수정 구간 조회] 를 합 니 다. [구간 수정 구간 조회] 도 할 수 있 지만 싫 습 니 다. 아무튼 트 리 배열 의 한계 가 큽 니 다.근 데 왜 배 워 요?선분 나무 보다 상수 가 작 구나!그리고 코드 는 그 짧 은 몇 줄!!
크 크, 그리고 선분 나무: 선분 나무의 용 도 는 나무 모양 의 배열 보다 훨씬 크 고 상대 적 인 코드 량 도 비교적 크다.하지만 RMQ 같은 많은 것 을 지 킬 수 있 습 니 다.
다음은 예제 QwQ 입 니 다.
T1: codevs 1080 선분 트 리 연습
점 수정 구간 조회, 트 리 배열 누 드 문제.원 시퀀스 를 직접 유지 합 니 다.템 플 릿 첨부:

#include<cstdio>
#include<queue> 
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int size=12450*12;
ll bit[size];
ll sum(int i)
{
    ll ans=0;
    while(i>0)
    {
        ans+=bit[i];
        i-=i&-i;
    }
    return ans;
}
int n;
void add(int i,int x)
{
    while(i<=n)
    {
        bit[i]+=(ll)x;
        i+=i&-i;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a;scanf("%d",&a);
        add(i,a);
    }
    int m;scanf("%d",&m);
    while(m--)
    {
        int s;scanf("%d",&s);
        int a,b,c;
        if(s==1)
        {
            scanf("%d%d",&a,&c);
            add(a,c);
        }
        else
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",sum(b)-sum(a-1));
        }
    }
    return 0;
}

T2: codevs 1081 선분 트 리 연습 2
구간 수정 점 조회, 트 리 배열 누 드 문제.유지 보수 하 는 수열 이 새 수열 로 바 뀌 었 습 니 다.템 플 릿 첨부:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int size=100010;
int bit[size],n,num[size];
void add(int x,int d)
{
    for(int i=x;i<=n;i+=i&-i)
    {
        bit[i]+=d;
    }
}
int ask(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=i&-i)
    {
        ans+=bit[i];
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
    }
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int s;
        scanf("%d",&s);
        if(s==1)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,c);
            add(b+1,-c);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d
",num[x]+ask(x));
        }
    }
    return 0;
}

T3： poj3468 A Simple Problem with Integers
선분 수 누 드 문제, 구간 수정 구간 조회.근 데 내 가 위 에서 말 했 잖 아. 나무 모양 배열 도 할 수 있다 고. 여 기 는 말 하고 싶 지 않 아. 너무 귀 찮 으 니까..
부 선분 트 리 템 플 릿:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int size=100010;
typedef long long ll;
struct segment{
    int l,r;
    ll sum,add;
}tree[size*4];

void updata(int p)
{
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void build(int p,int l,int r)
{
    tree[p].l=l;
    tree[p].r=r;
    if(l==r)
    {
        scanf("%lld",&tree[p].sum);
        return ;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    updata(p);
}

void spread(int p)
{
    if(tree[p].add)
    {
        tree[p*2].add+=tree[p].add;
        tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);
        tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);
        tree[p*2+1].add+=tree[p].add;
        tree[p].add=0;
    }
}

void change(int p,int l,int r,ll d)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        tree[p].add+=d;
        tree[p].sum+=d*(tree[p].r-tree[p].l+1);
        return ;
    }
    spread(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) change(p*2,l,r,d);
    if(mid<r) change(p*2+1,l,r,d);
    updata(p);
}
ll ask(int p,int l,int r)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        return tree[p].sum;
    }
    spread(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    ll ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(mid<r) ans+=ask(p*2+1,l,r);
    return ans;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        char s;
        cin>>s;
        int a,b;
        scanf("%d%d",&a,&b);
        if(s=='Q')
        {
            printf("%lld
",ask(1,a,b));
        }
        else
        {
            ll c;
            scanf("%lld",&c);
            change(1,a,b,c);
        }
    }
    return 0;
}

T4：
poj3321 Apple Tree
나무 한 그루 를 드 리 겠 습 니 다. 하나의 점 권 을 수정 하고 특정한 키 나무의 점 권 과 조 회 를 지원 하 라 고 요구 합 니 다.(구체 적 으로 문 제 를 보십시오)
트 리 배열 은 dfs 순 서 를 유지 하고 점 x 가 나타 난 첫 번 째 위치 pre [x] 와 두 번 째 로 나타 난 위치 suf [x] 를 기록 합 니 다. 이 두 위치 사이 의 모든 수 는 x 의 서브 트 리 입 니 다.따라서 트 리 배열 로 유지 하고 모든 suf [x] (또는 pre [x]) 를 1 로 초기 화하 고 수정 하면 suf [x] (또는 pre [x]) 만 수정 하 며 조 회 는 출력 [1, suf [x] - [1, pre [x]] 만 수정 하면 됩 니 다.
코드:

#include<cstdio>
#include<iostream>
using namespace std;
const int size=200010;
int head[size],nxt[size],to[size],tot=0;
int n;
void build(int f,int t)
{
    to[++tot]=t;
    nxt[tot]=head[f];
    head[f]=tot;
}
int pre[size],suf[size],clock=0;
int bit[size*2];

void add(int x,int d)
{
    for(int i=x;i<=clock;i+=i&(-i))
    {
        bit[i]+=d;
    }
}
bool vis[size];
void dfs(int u)
{
    pre[u]=++clock;
    vis[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!vis[v]) dfs(v);
    }
    suf[u]=++clock;
}
int sum(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=i&-i)
    {
        ans+=bit[i];
    }
    return ans;
}
bool ss[size];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        build(a,b);
        build(b,a);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        add(suf[i],1);
    }
/* puts(""); for(int i=1;i<=n;i++) { cout<<pre[i]<<" "<<suf[i]<<endl; }*/

    int m;
    scanf("%d",&m);
    while(m--)
    {
        char s;
        int x;
        cin>>s;
        scanf("%d",&x);
        if(s=='C')
        {
            if(!ss[x])
            {
                add(suf[x],-1);
                ss[x]=1;
            }
            else
            {
                add(suf[x],1);
                ss[x]=0;                
            }
        }
        else
        {
            printf("%d
",sum(suf[x])-sum(pre[x]));
        }
    }
    return 0;
}

/* 5 1 2 2 3 3 4 4 5 10 Q 1 */

T5：
poj2352 Stars
n 개의 별의 좌표 x, y 를 드 리 겠 습 니 다. 별의 등급 은 [이 별 왼쪽 아래 에 있 는 별 개수 (현재 줄 과 열 포함)] 이 고 출력 등급 은 0 에서 n - 1 의 별 개수 입 니 다.입력 보증 은 오름차 순, y 는 같은 x 오름차 순 입 니 다.[지금까지 평면 직각 좌표계 에서]
얼핏 보면 2 차원 나무 모양 배열!데이터 범위 다시 보기: 1w5 QAQ
입력 에 이상 한 특성 이 있 습 니 다.별 u 의 등급 = u 의 x 좌표 보다 작은 입력 된 별의 개수 입 니 다.그래서 1 차원 문제 로 바 뀌 었 고 나무 모양 의 배열 이 유지 되 었 다.아, 맞아요. 좌표 가 0 일 수도 있 으 니 트 리 배열 을 유지 할 때 + 1 을 잊 지 마 세 요.참고 로 정렬 은 2 차원 문 제 를 1 차원 문제 로 바 꿀 수 있다.
코드 가 좀 방자 해서 450 원 을 냈 습 니 다.

#include<cstdio>
#include<iostream>
using namespace std;
const int size=12450;
int bit[size * 9],ans[size * 9];

void add(int x,int d)
{
    for(int i=x;i<=size * 3 + 450;i+=i&-i)
    {
        bit[i]+=d;
    }
}

int ask(int x)
{
    int ans=0;
    for(int i=x;i;i-=i&-i)
    {
        ans+=bit[i];
    }
    return ans;
}
void scan(int &n)
{
    n=0;
    char a=getchar();
    while(a<'0'||a>'9') a=getchar();
    while(a>='0'&&a<='9') n*=10,n+=a-'0',a=getchar();
}

int main()
{
    int n;
    scan(n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scan(x);scan(y);
        ans[ask(x+1)]++;
        add(x+1,1);
    }

    for(int i=0;i<=n-1;i++)
    printf("%d
",ans[i]);
    return 0;
}

먼저 이것들 을 합 시다. 또 새로운 단독 QwQ 가 있 습 니 다.