선분 수 입문 상세 설명

목차

선분 수 입문 상세 설명

본 고의 적용 대상

선분 나무의 대체적인 사고방식

본인 코드 습관

단점 수정

단점 조회

구간 조회

구간 가감

Last

선분 수 입문 상세 설명
본문 은 사람들 에 게 적용 된다.
특별히 입문 한 것 은 아 닙 니 다 ~. 본 고 는 선분 나무의 원 리 를 대충 알 고 있 는 것 에 적합 하지만 선분 나무의 조작 에 익숙 하지 않 은 oier or Acmer 입 니 다. 본인 의 수준 이 유한 하고 데이터 구 조 를 깊이 연구 하지 않 았 습 니 다. 큰 신 은 뿌리 지 마 세 요. 궁금 한 점 이 있 으 면 바로 댓 글 에서 말씀 하 세 요. 감사합니다. 잘못 이 있 으 면 지적 해 주세요.
선분 수 대체적인 사고방식
데이터 범위 가 \ (nlog n \) 인 시퀀스 를 보 았 습 니 다. 크게 선분 트 리 로 만 들 었 습 니 다. 선분 트 리 문 제 를 푸 는 방법 1. 문 제 를 수학 식 으로 줄 이 고 유지 할 수 있 는 것 으로 만 듭 니 다. 2. 그 정 보 를 지 키 는 것 을 고려 합 니 다. 3. 어떻게 합 치 는 지 4. 어떻게 내 려 놓 는 지 5. 어떻게 조회 하 는 지
본인 코드 습관
코드 를 이해 하기 위해 서 특별히 설명 합 니 다.

struct Seg {
    int l,r,sum;
    int lazy;
}tree[];

l 현재 관할 구간 의 왼쪽 끝 점 r 를 유지 하고 현재 관할 구간 의 오른쪽 끝 점 sum 유지 구간 과 lazy 를 유지 하 는 것 은 게 으 름 표시 입 니 다.

#define lson now << 1
#define rson now << 1 | 1

void build(int l,int r,int now) {
    tree[now].l = l;tree[now].r = r;
    if(l == r) {
        XXX;
        return;
    }
    int mid = (l + r) >> 1;
    build(l,r,lson);
    build(l,r,rson);
    updata(now);
}

이상 은 트 리 를 만 드 는 과정 입 니 다. now 는 현재 노드 lson 은 왼쪽 아이 rson 이 고 오른쪽 아이 updatea 는 아버지 에 게 노드 정 보 를 올 리 는 함수 입 니 다. 예 를 들 어 구간 과 이 updatea 함수 는

void updata(int now) {
    tree[now].sum = tree[lson].sum + tree[rson].sum;
    return;
}

다른 함수 가 있 으 면 다음 글 에서 설명 하 겠 습 니 다.
단점 수정
단점 수정.

void change(int pos,int val,int now) {
    if(tree[now].l == tree[now].r) {
        tree[now].sum += val;
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(pos <= mid) change(pos,val,lson);
    else change(pos,val,rson);
    updata(now);
    return;
}

이 함 수 는 이해 하기 가 매우 쉽 습 니 다. 만약 에 조회 한 위치 가 왼쪽 아들 의 관할 범위 에 있다 면 왼쪽 아들 에 게 가서 수정 하 세 요. 오른쪽 아들 은 똑 같 습 니 다. updata 함 수 는 잊 지 마 세 요. 위의 정보 도 수정 해 야 합 니 다. 함 수 를 수정 하려 면 updata 가 필요 합 니 다. 잊 지 마 세 요. 다음은 네 개의 선분 트 리 간 단 함수 의 예 입 니 다.
단일 지점 조회
위의 한 점 수정 과 같 습 니 다. 코드 를 주의 하 세 요. 할 말 이 없습니다. 아마도 선분 트 리 의 가장 간단 한 함수 일 것 입 니 다.

int find(int pos,int now) {
    if(tree[now].l == tree[now].r) {
        return tree[now].sum;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(pos <= mid) return find(pos,lson);
    else return find(pos,rson);
}

구간 조회
모든 선분 트 리 의 점 은 구간 의 완전한 정 보 를 유지 하기 때 문 입 니 다. 이 점 은 구간 정 보 를 유지 하 는 구간 이 완전히 조회 구간 범위 내 에서 만 답 에 기여 할 수 있 습 니 다. 그렇지 않 으 면 계속 나 눌 수 있 습 니 다. 여 기 는 구간 의 합 을 조회 합 니 다.

int query(int l,int r,int now) {
    if(tree[now].l >= l && tree[now].r <= r) 
        return tree[now].sum;
    int mid = (tree[now].l + tree[now].r) >> 1,sum = 0;
    if(mid >= l ) sum += query(l,r,lson);
    if(mid < r) sum += query(l,r,rson);
    return sum;
}

이 부분의 함 수 는 이해 하기 어렵다. 여기 서 구간 을 어떻게 판단 하고 교 제 를 구 하 는 지 에 중점 을 두 고 설명 한다. 여기 서 now 노드 를 조회 하면,계속 나 누 어 조회 해 야 합 니 다. now 관할 구간 은 반드시 조회 구간 과 교 집합 되 어 있 음 을 설명 합 니 다. 여기 서 고려 하 는 것 은 왼쪽 아들 과 조회 해 야 할 구간 이 교 집합 되 어 있 는 지, 오른쪽 아들 과 조회 해 야 할 구간 이 교 집합 되 어 있 는 지 없 는 지 를 고려 하여 아래 의 if 판단 이 있 습 니 다. 합 쳐 진 정 보 를 위로 전달 하 는 것 에 주의 하 세 요.
구간 가감
이 럴 때 는 게 으 름 표 시 를 사용 해 야 합 니 다. 게 으 름 표 시 는 아주 신기 한 것 입 니 다. 게 으 름 표 시 는 시간 을 끌 어 내 리 는 것 을 중시 합 니 다. 구간 이 줄 어 들 때 폭력 업데이트 보다 \ (n ^ 2 \) 알고리즘 이 낫 습 니 다. 게 으 름 표 시 는 구간 을 해결 하 는 것 입 니 다. 게 으 름 표 시 를 사용 하 는 것: 검색, 조작 은 물론 이 고 모두 표 시 를 내 려 놓 아야 합 니 다. 왜 요?하 나 는 비교적 편리 하고 조작 하기 쉬 우 며, 나머지 하 나 는 상 관 없 이, 다른 하 나 는 작업 순서 와 관련 된 것 이다. 예 를 들 어 구간 할당 값 이 1 값 이 되 는 것 이다. 어떻게 하 나 를 표시 합 니까?제목 을 보고 정 합 니 다. 어떤 문 제 는 여러 개의 표 시 를 해 야 합 니 다. 표 시 된 우선 순 위 를 생각해 보 세 요. 이렇게 하면 세 개의 함수 가 더 많아 집 니 다. pushdown 과 modify 와 work 여기 의 lazy 표 시 는 추가 해 야 할 값 입 니 다. 세 개의 함수 에 대한 소개 입 니 다. work 함수

void work(int now , int val) {
    tree[now].sum += (tree[now].r - tree[now].l + 1) * val;
    tree[now].lazy += val;
}

이 함 수 는 now 선분 트 리 노드 가 관할 하 는 구간 에 하나의 수 를 더 하 는 것 입 니 다. pushdown 함수

void pushdown(int now) {
    work(lson,tree[now].lazy);
    work(rson,tree[now].lazy);
    tree[now].lazy = 0;
    return;
}

pushodown 함 수 는 할 말 이 없습니다.

void modify(int l,int r,int now,int val) {
    if(tree[now].l >= l && tree[now].r <= r) {
        work(now,val);
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(tree[now].lazy) pushdown(now);
    if(mid >= l ) modify(l,r,lson,val);
    if(mid < r) modify(l,r,rson,val);
    updata(now);
    return ;
}

그런데 이게 다 야..
Last
선분 트 리 는 가장 자주 사용 하 는 데이터 기구 중 하나 입 니 다. 매우 많은 세트 는 나중에 일일이 열거 할 것 입 니 다. 다음은 몇 개의 예제 템 플 릿 문 제 를 제시 하여 자신 이 1. 템 플 릿 트 리 모양 배열 1. 템 플 릿 트 리 모양 배열 2. 템 플 릿 선분 트 리 1. 템 플 릿 선분 트 리 25. 간단 한 선분 트 리 템 플 릿 문제 입 니 다.
1. 템 플 릿 문제

#include 
#include 
const int maxN = 1e6 + 7;

int a[maxN];

inline int max(int x,int y) {
    return x > y ? x : y;
} 

struct Node{
    int l,r,maxx;
    int w;
}tree[maxN << 2];

void pushup(int now) {
    tree[now].w = tree[now << 1].w + tree[now << 1 | 1].w;
    tree[now].maxx = max(tree[now << 1].maxx,tree[now << 1 | 1].maxx);
}

void build(int now,int l,int r) {
    tree[now].l = l;tree[now].r = r;
    if(l == r) {tree[now].w = a[l];return;}
    int mid = (l + r) >> 1;
    build(now << 1,l,mid);
    build(now << 1 | 1,mid + 1,r);
    pushup(now); 
}

int query(int l,int r,int now) {
    if(tree[now].l >= l && tree[now].r <= r) return tree[now].w;
    int Ans = 0;
    int mid = (tree[now].r + tree[now].l) >> 1;
    if(mid >= l) {Ans += query(l,r,now << 1);}
    if(mid < r) {Ans += query(l,r,now << 1 | 1);}
    return Ans;
}

inline int read() {
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}

void chang(int x,int now,int pos) {
    tree[now].w += x;
    if(tree[now].l == tree[now].r) return;
    int mid = (tree[now].r + tree[now].l) >> 1;
    if(mid >= pos) chang(x,now << 1,pos);
    else chang(x,now << 1 | 1,pos); 
    return;
}
int main() {
    int n,m;
    n = read();m = read();
    for(int i = 1;i <= n;++ i) 
        a[i] = read();
    build(1,1,n); 
    for(int i = 1,emm,l,r;i <= m;++ i) {
        emm = read();
        l = read();r = read();
        if(emm == 1)chang(r,1,l);
        else printf("%d
",query(l,r,1));
    }
    return 0;
}

2. 템 플 릿 문제

#include 
#include 
#define X 500007

struct  Node{
    int l,r,w,lazy;
}tree[X << 2];

void update(int now){
    tree[now].w = tree[now << 1].w + tree[now << 1 | 1].w;
    return;
}

void down(int now){
    int lazy = tree[now].lazy;
    if(lazy){
        tree[now << 1].lazy += lazy;
        tree[now << 1 | 1].lazy += lazy;
        tree[now << 1].w += lazy * (tree[now << 1].r - tree[now << 1].l + 1);
        tree[now << 1 | 1].w += lazy * (tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1);
        tree[now].lazy = 0;
    }
}

void build(int l,int r,int now){
    tree[now].l = l;tree[now].r = r;
    if(l == r){
        scanf("%d",&tree[now].w);
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,now << 1);
    build(mid + 1,r,now << 1 | 1);
    update(now);
}

void add_inter(int l,int r,int now,int val){
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].w += val * (tree[now].r - tree[now].l + 1);
        tree[now].lazy += val;
        return;
    }
    int mid = (tree[now].l + tree[now].r ) >> 1;
    if(l <= mid){add_inter(l,r,now << 1,val);}
    if(r > mid){add_inter(l,r,now << 1 | 1,val);}
    update(now);
    return;
}

int Point_ask(int pos,int now){
    if(tree[now].l == tree[now].r){
        return tree[now].w;
    }
    down(now);
    int mid = (tree[now].r + tree[now].l) >> 1;
    if(pos <= mid)return Point_ask(pos,now << 1);
    else return Point_ask(pos,now << 1 | 1);
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i = 1,x;i <= m;++ i){
        scanf("%d",&x);
        if(x == 1){
            int l,r,val;
            scanf("%d%d%d",&l,&r,&val);
            add_inter(l,r,1,val);
        }else{
            int xx;
            scanf("%d",&xx);
            printf("%d
",Point_ask(xx,1));
        }
    }
}

3. 템 플 릿 문제

#include 
#include 
const int maxN = 1e5 + 7; 
#define ll long long

inline int read() {
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}

struct Node{
    ll l,r,w,lazy;
}tree[maxN << 2];
ll a[maxN];

void pushdown(ll now) {
    ll lazy = tree[now].lazy;
    tree[now].lazy = 0;
    tree[now << 1].lazy += lazy;
    tree[now << 1 | 1].lazy += lazy;
    tree[now << 1].w += (tree[now << 1].r - tree[now << 1].l + 1) * lazy;
    tree[now << 1 | 1].w += (tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1) * lazy;
    return; 
} 

void updata(ll now) {
    tree[now].w = tree[now << 1].w + tree[now << 1 | 1].w; 
}

void build(ll l,ll r,ll now) {
    tree[now].l = l;tree[now].r = r;
    if(l == r) {
        tree[now].w = a[l];
        return;
    } 
    ll mid = (l + r ) >> 1;
    build(l,mid,now << 1);
    build(mid + 1,r,now << 1 | 1);
    updata(now);
}

void Inter_add(ll l,ll r,ll now,ll val) {
    if(tree[now].l >= l && tree[now].r <= r) {
        tree[now].w += (tree[now].r - tree[now].l + 1) * val;
        tree[now].lazy += val;
        return;
    }
    pushdown(now); 
    ll mid = (tree[now].l + tree[now].r) >> 1;
    if(l <= mid) Inter_add(l,r,now << 1,val);
    if(r > mid) Inter_add(l,r,now << 1 | 1,val);
    updata(now);
    return;
}

ll query(ll l,ll r,ll now) {
    if(tree[now].l >= l && tree[now].r <= r) {
        return  tree[now].w;
    }
    if(tree[now].lazy)pushdown(now);
    ll Ans = 0;
    ll mid = (tree[now].l + tree[now].r) >> 1;
    if(l <= mid) Ans += query(l,r,now << 1);
    if(r > mid ) Ans += query(l,r,now << 1 | 1); 
    return Ans;
}

int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;++ i) 
        a[i] = read();
    build(1,n,1);
    for(int i = 1,opt,l,r;i <= m;++ i)  {
        opt = read();l = read();r = read();
        if(opt == 1) {
            ll val;
            val = read();
            Inter_add(l,r,1,val);
        }
        if(opt == 2) {
            printf("%lld
",query(l,r,1));
        }
    }
    return 0;
} 

덧셈 표기 와 곱셈 표기 의 우선 순 위 를 주의 하 십시오. 여기 서 곱셈 표기 의 우선 순 위 를 사용 하여 업 데 이 트 를 진행 합 니 다.

#include 
#include 
#define ll long long
const ll maxN = 100000 + 7;

using namespace std;
ll a[maxN];
ll mod;

struct Node{
    ll l,r,sum;
    ll mul,add;
    Node() {
        add = sum = 0;mul = 1;
    }
}tree[maxN << 2];

void qwq(ll now,ll mul,ll add) {
    tree[now].mul = tree[now].mul * mul % mod;
    tree[now].add = ( tree[now].add * mul % mod + add) % mod;
    tree[now].sum = ( (tree[now].sum * mul) % mod +(  (tree[now].r - tree[now].l + 1) * add) % mod ) % mod; 
}

void updata(ll now) {
    tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
    return;
}

void pushdown(ll now) {
    qwq(now << 1,tree[now].mul,tree[now].add);
    qwq(now << 1 | 1,tree[now].mul,tree[now].add);
    tree[now].mul = 1;
    tree[now].add = 0;
}

void build(ll l,ll r,ll now) {
    tree[now].l = l;tree[now].r = r;
    if(l == r) {
        tree[now].sum = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(l,mid,now << 1);
    build(mid + 1,r,now << 1 | 1);
    updata(now);
}

ll query(ll L,ll R,ll now) {
    ll l = tree[now].l ,r = tree[now].r;
    if(l >= L && r <= R) return tree[now].sum % mod;
    if(tree[now].add || tree[now].mul != 1) pushdown(now);
    ll sum = 0;
    if(L <= (r + l ) >> 1) sum += query(L,R,now << 1);sum %= mod;
    if(R > (r + l ) >> 1) sum += query(L,R,now << 1 | 1);
    return sum % mod;
}

void Inter_change(ll L,ll R,ll now,ll add,ll mul) {
    ll l = tree[now].l,r = tree[now].r;
    if(l >= L && r <= R) {
        qwq(now,mul,add);
        return;
    }
    ll mid = (r + l) >> 1;
    if(tree[now].add || tree[now].mul != 1) pushdown(now);
    if(L <= mid) Inter_change(L,R,now << 1,add,mul);
    if(R > mid) Inter_change(L,R,now << 1 | 1,add,mul);
    updata(now);
}

int main()
{
    ll n,m;
    scanf("%lld%lld%lld",&n,&m,&mod);
    for(ll i = 1;i <= n;++ i) 
        scanf("%lld",&a[i]);
    build(1,n,1);
    ll opt,l,r,k;
    while(m --) {
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt != 3) {
            scanf("%lld",&k);
            if(opt == 1) {
                Inter_change(l,r,1,0,k);
            }
            if(opt == 2) {
                Inter_change(l,r,1,k,1);
            }
        }
        else printf("%lld
", query(l,r,1));
    }
    return 0;
}

간단 한 식 자 는 한 개의 수 를 곱 하고 한 개의 수 를 더 할 때 어떻게 업데이트 하 는 지 주의 하 십시오. 업데이트 의 우선 순위 에 주의 하 십시오.

#include 
#include 
#define lson now << 1
#define rson now << 1 | 1
#define ll long long
const ll maxN = 10000 + 7;
 
struct Node {
    ll l,r;
    ll sum[3];
    ll lazy,tag;
}tree[maxN << 2];
 
void updata(ll now) {
    tree[now].sum[1] = tree[lson].sum[1] + tree[rson].sum[1];
    tree[now].sum[2] = tree[lson].sum[2] + tree[rson].sum[2];
    return ;
}
 
void build(ll l,ll r,ll now) {
    tree[now].l = l;tree[now].r = r;
    tree[now].tag = 1;
    if(l == r) {
        scanf("%d",&tree[now].sum[1]);
        tree[now].sum[2] = tree[now].sum[1] * tree[now].sum[1];
        return;
    }
    ll mid = (l + r) >> 1;
    build(l,mid,lson);
    build(mid + 1,r,rson);
    updata(now);
    return;
}
 
void work(ll now,ll lazy,ll tag) {
    tree[now].sum[2] = tree[now].sum[2] * tag;
    tree[now].sum[1] = tree[now].sum[1] * tag;
    tree[now].sum[2] += 2 * tree[now].sum[1] * lazy + (tree[now].r - tree[now].l + 1) * lazy * lazy;
    tree[now].sum[1] += (tree[now].r - tree[now]. l + 1) * lazy;
    tree[now].lazy = tree[now].lazy * tag + lazy;
    tree[now].tag *= tag;
    return;
}
 
void pushdown(ll now) {
    work(lson,tree[now].lazy,tree[now].tag);
    work(rson,tree[now].lazy,tree[now].tag);
    tree[now].lazy = 0;
    tree[now].tag = 1;
    return ;
}
 
ll query_1(ll l,ll r,ll now) {
    if(tree[now].l >= l && tree[now].r <= r)
        return tree[now].sum[1];
    ll mid = (tree[now].l + tree[now].r) >> 1,sum = 0;
    if(tree[now].lazy || tree[now].tag != 1) pushdown(now);
    if(mid >= l) sum += query_1(l,r,lson);
    if(mid < r) sum += query_1(l,r,rson);
    return sum;
}
 
ll query_2(ll l,ll r,ll now) {
    if(tree[now].l >= l && tree[now].r <= r)
        return tree[now].sum[2];
    ll mid = (tree[now].l + tree[now].r) >> 1,sum = 0;
    if(tree[now].lazy || tree[now].tag != 1) pushdown(now);
    if(mid >= l) sum += query_2(l,r,lson);
    if(mid < r) sum += query_2(l,r,rson);
    return sum;
}
 
void modify(ll l,ll r,ll now,ll lazy,ll tag) {
    if(tree[now].l >= l && tree[now].r <= r) {
        work(now,lazy,tag);
        return ;
    }
    ll mid = (tree[now].l + tree[now].r) >> 1;
    if(tree[now].lazy || tree[now].tag != 1) pushdown(now);
    if(mid >= l) modify(l,r,lson,lazy,tag);
    if(mid < r) modify(l,r,rson,lazy,tag);
    updata(now);
    return ;
}
 
int main() {
    ll n,m;
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    ll opt,l,r,x;
    while(m --) {
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt == 1) printf("%lld
",query_1(l,r,1));
        if(opt == 2) printf("%lld
", query_2(l,r,1));
        if(opt == 3) {
            scanf("%lld",&x);
            modify(l,r,1,0,x);
        }
        if(opt == 4) {
            scanf("%lld",&x);
            modify(l,r,1,x,1);
        }
    }
    return 0;
}

여기 우리 문제 하나 더 있 는데 풀 어 볼 까요? 어떤 문제 가 잊 어 버 렸 는 지. 문제.

0 l r     [l,r]     
1 l r     [l,r]         
2 l r     [l,r]         
3 l r x    [l,r]          x
4 l r x    [l,r]          x
5.l r x    [l,r]          x

시간 이 있 으 면 그것 을 개인 문제 창고 에 걸 고 시간 이 있 으 면 선분 트 리 의 진급 을 업데이트 할 것 입 니 다.
다음으로 전송:https://www.cnblogs.com/tpgzy/p/9751518.html