데이터 구조 선분 트 리 와 트 리 배열

선분 수
Reference:https://www.cnblogs.com/AC-King/p/7789013.html
해결 해 야 할 문제:
1. 구간 [L, R] 사이 의 최대 값 조회
2. a [i] 를 x 로 수정 합 니 다.
 
명확 하 게 해결 할 수 있 는 문제:
구간 의 가산 성 을 만족 시 키 는 문제 여야 한다. 예 를 들 어:

         ：
    ——      =         +        
     (GCD)—— GCD = gcd(    GCD ,    GCD );
   ——    =max(      ，      )
          ：
  ——          ，         
01        ——             ，           

 
 
선분 트 리 의 구축

#include 
using namespace std;
const int maxn = 110;
int a[maxn];
int minv[4 * maxn];
void pushup(int id) {
    minv[id] = min(minv[id << 1],minv[id << 1 | 1]);
}
void build(int id,int l,int r) {
    if(l == r) {
        minv[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
int main() {
    int n;
    cin >> n;
    for(int i = 1;i <= n; ++i) {
        cin >> a[i];
    }
    build(1,1,n);
    return 0;
}

2. 선분 트 리 의 단일 업데이트

#include 
using namespace std;
const int maxn = 110;
int a[maxn];
int minv[4 * maxn];
void pushup(int id) {
    minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}
void build(int id, int l, int r) {
    if (l == r) {
        minv[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
void update(int id,int l,int r,int x,int v) {
    if(l == r) {
        minv[id] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) {
        update(id << 1, l, mid, x, v);
    }else {
        update(id << 1 | 1, mid + 1, r, x ,v);
    }
    pushup(id);
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);
    int q;
	cin >> q;
    for(int i = 0;i < q; ++i) {
        int x,v;
        cin >> x >> v;
        update(1, 1, n, x, v);
    }
    
    return 0;
}

3. 선분 트 리 구간 조회

#include 
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int a[maxn];
int minv[4 * maxn];
void pushup(int id) {
    minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}
void build(int id, int l, int r) {
    if (l == r) {
        minv[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
void update(int id, int l, int r, int x, int v) {
    if (l == r) {
        minv[id] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        update(id << 1, l, mid, x, v);
    } else {
        update(id << 1 | 1, mid + 1, r, x, v);
    }
    pushup(id);
}
int query(int id, int l, int r, int x, int y) { //     
    if(x <= l && r <= y) {
        return minv[id];
    }
    int mid = (l + r) >> 1;
	int ans = inf;
    if(x <= mid) {
        ans = min(ans,query(id << 1,l, mid, x, y));
    }
    if(y > mid) {
        ans = min(ans, query(id << 1 | 1,mid + 1, r, x, y));
    }
    return ans;
}
int query(int id, int l, int r, int x) { //    
    if (l == r) {
        return minv[id];
    }
    int mid = (l + r) >> 1;
    if (mid <= x) {
        return query(id << 1, l, mid, x);
    } else {
        return query(id << 1 | 1, mid + 1, r, x);
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int x, v;
        cin >> x >> v;
        update(1, 1, n, x, v);
    }
    int p;
    cin >> p;
    for(int i = 0;i < p; ++i){
        int l, r;
        cin >> l >> r;
        cout << query(1,1,n,l,r) << endl;
    }
    return 0;
}

2. 나무 모양 배열
1. lowbit 구하 기

lowboy(x) = x & (-x);

2. 조회 및 업데이트

#include 
using namespace std;
const int maxn = 110;
int C[maxn], n;
int lowbit(int x) {
    return x &(-x);
} 
int getsum(int x) {
    int res = 0;
    for(int i = x;i > 0; i-=lowbit(i)) {
		res += C[i];        
    }
    return res;
}
void update(int x,int v) {
    for(int i = x; i <= n; i+= lowbit(i)) {
        C[i] += v;
    }
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int v;
        cin >> v;
    	update(i,v);
    }
    int q;
    cin >> q;
    while(q--) {
        int l,r;
        cin >> l>> r;
        cout << getsum(r) - getsum(l - 1) << endl;
    }
    return 0;    
}

 
분할 선
몇 가지 입문 문제:
1.
제목: POJ 3264 http://poj.org/problem?id=3264
해답:https://blog.csdn.net/Sensente/article/details/100799498
2.
제목: HDU 1754 http://acm.hdu.edu.cn/showproblem.php?pid=1754
해답:https://blog.csdn.net/Sensente/article/details/100822674
3.
제목: HDU 1166 http://acm.hdu.edu.cn/showproblem.php?pid=1166
해답:https://blog.csdn.net/Sensente/article/details/100829978
4.
제목: HDU 1698 Just a Hook (시간 지연 표시 선분 트 리)
해답:https://blog.csdn.net/Sensente/article/details/100890962