[선분 수] 구간 문제 에 대하 여 말씀 드 리 겠 습 니 다 (1)

문장 은 다음 과 같은 내용 을 언급 할 것 이다
1. 선분 트 리, O (n) - O (qlogn) online.2、ST（Sparse Table），O(nlogn)-O(q) online。
1. 선분 트 리
2 분 의 사상 을 이용 하여 원 하 는 구간 을 2 분 으로 나 누 어 시간 대 가 를 소박 O (n ^ 2) 에서 O (nlogn) 등급 으로 최적화 시킨다.아래 의 위의 누 드 문 제 는 이해 하기 쉽다.시간 대가 O (2 * n – 구조 트 리 + q * logn – q 그룹 조회).
동적 통계 1
[문제 설명] n 개의 요 소 를 포함 하 는 정수 배열 A 가 있 습 니 다. A 에 대해 다음 과 같은 두 가지 조작 을 할 수 있 습 니 다. 1. 하나의 요 소 를 수정 하고 modify a b, 예 를 들 어 modify 1 3, 즉 A [1] 를 32 로 바 꾸 면 query a b, 예 를 들 어 query 1 3 즉 조회 구간 [1, 3] 안의 모든 요소 의 합 을 조회 할 수 있 습 니 다.첫 줄 의 정수 n, m 를 입력 하 십시오.다음 n 개 는 1000 보다 크 지 않 은 수 입 니 다.마지막 으로 m 줄 마다 하나의 동작 을 표시 합 니 다. 형식 은 modify a b 또는 query a b 출력 으로 Query a b 의 값 을 순서대로 출력 합 니 다.
[문제 분석] 무 ~ ~ ~ ~

#include <iostream>
#include <cstdio>
using namespace std;
const int N=10001;
int n,m,top;  int num[N];
struct zk { int left,right,leftchild,rightchild,middle,sum; }; zk tree[N*2];
//left,right              ，            ，  ！！！
void read()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
        scanf("%d",&num[i]);
    tree[1].left=1; tree[1].right=n+1;
    top=1;
    return;
}
void build_a_tree(int k)
{
    if (tree[k].left==tree[k].right-1)
    {
        tree[k].sum=num[tree[k].left];
        return;
    }
    tree[k].middle=(tree[k].left+tree[k].right)/2;
    top++;
    tree[k].leftchild=top;
    tree[top].left=tree[k].left;
    tree[top].right=tree[k].middle;
    build_a_tree(top);
    top++;
    tree[k].rightchild=top;
    tree[top].left=tree[k].middle;
    tree[top].right=tree[k].right;
    build_a_tree(top);
    tree[k].sum=tree[tree[k].leftchild].sum+tree[tree[k].rightchild].sum;
    return;
}
int query(int a,int b,int k)
{
    if (a==tree[k].left&&b==tree[k].right-1)
        return tree[k].sum;
    else if (a>=tree[k].middle)
        return query(a,b,tree[k].rightchild);
    else if (b<tree[k].middle)
        return query(a,b,tree[k].leftchild);
    else
        return query(a,tree[k].middle-1,tree[k].leftchild)+query(tree[k].middle,b,tree[k].rightchild);
}
void modify(int a,int b,int k)
{
    if (tree[k].left==tree[k].right-1)
    {
        tree[k].sum=b;
        return;
    }
    if (tree[k].middle>a)   modify(a,b,tree[k].leftchild);
    else    modify(a,b,tree[k].rightchild);
    tree[k].sum=tree[tree[k].leftchild].sum+tree[tree[k].rightchild].sum;
    return;
}
void work()
{
    int i,a,b; char s[6];
    for (i=1;i<=m;i++)
    {
        scanf("%s%d%d",s,&a,&b);
        if (s[0]=='m') {modify(a,b,1);}
        else printf("%d
",query(a,b,1));
    }
    return;
}
int main()
{
    read();
    build_a_tree(1);
    work();
    return 0;
}

2.Sparse Table
특별 철♂배 운 알고리즘 은 선분 나무의 이분 사상 을 바탕 으로 dp 를 더 해 시간 대 가 를 불가사의 한 지경 까지 최적화 시 켰 다.두 번 째 원소 부터 시작 해서 길이 가 j ^ 2 인 구간 중 가장 큰 값 임 을 F [j] [j] [j] = max (dp[i]] [j]] [j]] [j ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ F [i] [j] 는 두 구간 의 가장 값 으로 구 할 수 있다 고 합 니 다.그래서 2 분 절약 시간 대가 O (nlogn – 구조 트 리 + q – 조회) 다음 에 조회 해 보 세 요.♂배우다주어진 구간 [a, b] 의 최대 치 를 요구 합 니 다. 이 구간 을 이미 알 고 있 는 가장 값 진 구간 (중첩 부분 이 있 을 수 있 고 답 에 영향 을 주지 않 습 니 다) 으로 나 눌 수 있 습 니 다. 이 두 구간 은 각각 [a, a + (t ^ 2)] 와 [b - t ^ 2, b] 입 니 다. 그리고 O (1) 대 가 를 꺼 내 면 됩 니 다. 그리고 구간 을 찾 으 면 2 ^ n 의 빠 른 계산 과 관련 되 어 최적화 할 수 있 습 니 다.
여기 게 으 름 피 우 면 코드 가 안 나 와...
이것 이 바로 비교적 간단 한 구간 문 제 를 구 하 는 방법 이다.그리고 신기 한 것 도 많아 요. 예 를 들 어 RMQ, 나무 모양 배열 등등...이 내용 들 은 다음 절 내용 에서 언급 될 것 이다.