트 리 배열 테마 총화

나무 모양 배열 은 우리 가 배 울 만 한 전형 적 인 구간 작업 이 많 습 니 다. 하나의 템 플 릿 에 해당 합 니 다. 이해 하기 도 쉽 고 나무 모양 배열 의 기능 도 강하 고 코드 도 간단 합 니 다. 그리고 선분 트 리 의 코드 량 이 많 고 오류 가 발생 하기 쉬 우 며 깊이 이해 하기 어렵 습 니 다. 그래서 저 는 먼저 나무 모양 배열 을 배 워 서 선분 트 리 를 준비 합 니 다. 선분 트 리 가 중요 하지 않 은 것 이 아 닙 니 다.선분 나무의 응용 이 더욱 광범 위 하기 때문에 이런 데이터 구조의 학습 도 반드시 깊이 들 어가 야 한다. 그러면 나 는 먼저 나무 모양 의 배열 을 정리 하 겠 다.
lowbit (x) 는 x 의 바 이 너 리 를 구 합 니 다. 마지막 으로 k 개 0 이 있 고 돌아 오 는 값 은 2 ^ k 입 니 다.
1. 구간 구 화 + 단점 수정 (단점 추가 또는 감소)
구간 구 화: 가장 간단 한 나무 모양 배열 작업 은 나무 모양 배열 의 지역 관리 작업 을 이용 하여 신속하게 구 할 수 있 는 [1, x] 의 접두사 와 [1, r] 의 합 을 구 할 때 [1, r], [1, l - 1] 만 요구 하기 때문에 [l, r] 의 합 = [1, r] - [1, l - 1] 을 요구 합 니 다.
단점 수정: 이 점 x 에서 마지막 점 (n) 까지 관할 하 는 구간 은 모두 수정 해 야 하기 때문에 x + = lowbit (x) 로 조작 하면 모든 x 가 관할 하 는 위 치 를 얻 을 수 있 습 니 다.

int getsum(int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[i];
        x-=lowbit(x);
    }
    return sum;
}
void update(int x,int val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}

2. 구간 수정 + 단점 값 구하 기
이것 은 먼저 차이 점 사상 을 소개 합 니 다. 이것 은 비교적 간단 할 수 있 기 때문에 대부분의 블 로 그 는 생략 한 것 입 니 다. 여기 서 조금 말씀 드 리 겠 습 니 다.
원수 조 a [1, 5]: 1, 3, 2, 4, 6
계차 그룹 c [1, 5]: 1, 2 - 1, 2, 2
차이 점 조 는 c [i] = a [i] - a [i - 1]   (1<=i)
그러면 우 리 는 a [2] = c [1] + c [2] 를 얻 을 수 있다.   a[3]=c[1]+c[2]+c[3]   a[i]=c[1]+c[2]....+c[n]
그러면 트 리 배열 의 구 화 는 효과 가 있 습 니 다. 다만 여기 c [i] 배열 의 의미 가 다 릅 니 다. 여 기 는 차이 점 이 있 는 원래 배열 이 업데이트 한 트 리 배열 이 어야 합 니 다. 그래서 a [i] = getsum (i).
구간 수정: [l, r] 의 수 에 val 을 추가 하면 차이 점 그룹의 정의 에 따라 a [l] 를 먼저 봅 니 다. a [l] + = val 이기 때문에 a [l] - a [l - 1] = val 은 l 점 에서 update (l. val) 를 업데이트 해 야 합 니 다. 그러면 a [l + 1]... a [r - 1] 의 수 는 요?그것들 이 모두 + val 이라는 것 을 알 수 있 기 때문에 그것들의 차 이 는 원래 의 것 이기 때문에 갱신 할 필요 가 없다.그리고 a [r] 와 a [r + 1], a [r] + = val, a [r + 1] - a [r] = - val, 따라서 update (r + 1, - val);
단일 검색: a [i] = getsum (i)
이것 은 간단 한 문제 다.
Time Limit: 100 MS     Memory Limit: 64 MB
문 제 를 내 는 사람 Acnext 은 또 뒤 집어 쓰 려 고 한다. 그 는 모두 가 할 수 있 는 간단 한 문 제 를 내야 한다. 만약 에 못 하 는 사람 이 있 으 면 뒤 집어 써 야 한다. 똑똑 한 너 는 이 간단 한 문 제 를 해결 해서 그 가 뒤 집어 쓰 는 것 을 피 할 수 있 니?
긴 n 을 드 리 겠 습 니 다.
그리고
n
개 조작, 조작 관련 구간 덧셈, 단일 조회
Input
첫 번 째 줄 에 숫자 n 을 입력, (1 ≤ n ≤ 50000)
두 번 째 줄 은 n 개의 정수, 두 번 째 줄 을 입력 하 십시오.
숫자
ai,(1≤ai≤109)
띄 어 쓰기
다음 n 줄 질문 을 입력 하고 줄 마다 네 개의 숫자 를 입력 하 십시오.
opt,l,r,c
하면, 만약, 만약...
[l, r] 의 숫자 를 모두 더하기
c
질문
ar 값 무시
l,c
)
Output
매번 질문 에 대해 한 줄 의 답 을 출력 합 니 다.
모든 데이터 가 int 범위 내 에서
Sample input and output
Sample Input
Sample Output

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

2
5

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n;
ll c[100009];
ll lowbit(ll x)
{
    return x&(-x);
}
ll getsum(ll x)
{
    ll sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
ll update(ll x,ll val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}
int main()
{
    ll op,l,r,val,a;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a);
        update(i,a);
        update(i+1,(-1)*a);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld%lld",&op,&l,&r,&val);
        if(op==0)
        {
            update(l,val);
            update(r+1,(-1)*val);
        }
        else
        {
            printf("%lld
",getsum(r));
        }
    }
}

원본 값 에 대해 서 는 구간 [i, i] 을 가정 하여 업데이트 할 수 있 습 니 다.
3 구간 수정 + 구간 구 화
2 의 차 점 수 를 바탕 으로 한 추론 이 필요 하 다.
a[1]+a[2]+a[3]+....+a[n]
=(c[1])+(c[1]+c[2])+....(c[1]+c[2]+....c[n])
=n*c[1]+(n-1)*c[2]+.....2*c[n-1]+c[n]
=n*(c[1]+c[2]+...+c[n])-(0*c[1]+1*c[2]+....(n-1)*c[n])
등식 쓰기 편 하도록 + (c [1] + c [2] +... + c [n]) - (c [1] + c [2] +... + c [n])
a[1]+a[2]+a[3]+....+a[n]
=(n+1)*(c[1]+c[2]+...+c[n])-(1*c[1]+2*c[2]+....n*c[n])
그러면 우 리 는 앞의 부분 이 바로 우리 의 차이 점 과 뒤의 부분 은 다른 차이 점 그룹 을 만들어 야 한 다 는 것 을 볼 수 있다.
그래서 원 차 점 수 를 c1 [] 로 하고 다른 하 나 는 c2 [] 로 한다.
그러면 구간 은 원래 의 차이 점 수 를 그대로 조작 하면 되 고 두 번 째 차이 점 수 는 c2 [i] = i * c [i] 여야 합 니 다.
또한 l 과 r + 1 을 수정 합 니 다. 이 두 곳 은 i * val 로 변 했 을 뿐 입 니 다. 그래서 [1, r] 의 구 화 = (r + 1) getsum (r) - getsum 2 (r) 를 구 합 니 다.
내 아래 코드 는 하나의 함수 로 직접 쓰 여 져 있 기 때문에 getsum 2 함 수 는 사실 합 쳐 진 것 이다. 이것 은 하나의 선분 수 구간 의 구 화 문 제 를 해결 하 는 것 이다.
평범한 선분 나무
출제 자 는 내일 반 기 시험 이 있 습 니 다. 수업 은 입 니 다. 출제 자 는 피바다 에 쓰 러 졌 습 니 다. 힘 있 는 손 으로 출제 자의 어깨 를 흔 들 었 습 니 다. "동지, 정신 차 려 요. 아직 문제 가 끝나 지 않 았 어 요." 다음은 그의 유언 입 니 다.
배열 A [1. n] 하나 드릴 게 요.
초기 값 은 모두 0 입 니 다. 누 드 구간 수정, 구간 조회 의 선분 트 리 를 써 서 두 작업 을 지원 해 야 합 니 다. 첫 번 째 작업 은 구간 에 대한 것 입 니 다.
[L, R] 안에 있 는 숫자 에 숫자 를 더 해 주세요.
v. 두 번 째 조작 은 구간 을 제시 하 는 것 이다.
[L,R]
내 모든 수의 합.
Input
첫 번 째 줄 은 두 개의 정수 n (1 ≤ n ≤ 106) 을 포함한다.
화해시키다
m(1≤m≤106)
각각 배열 의 크기 와 작업 의 개수 입 니 다.
다음 m 줄, 줄 마다 네 개의 빈 칸 으로 구 분 된 정수
o l r v (1 ≤ l ≤ r ≤ n, | v | ≤ 103). 만약
구간
[l, r] 내 각 수 를 더 하 다
v. 그렇지 않 으 면 구간 을 제시 하 세 요.
[l, r] 내 모든 수의 합, 이때
v≡0
.
Output
각각 o ≠ 0
의 조작, 출력 은 하나의 정 수 를 포함 하 는 한 줄 로 해당 구간 내의 모든 수의 합 을 나타 낸다.
Sample input and output
Sample Input
Sample Output

5 4
0 2 4 5
1 3 5 0
0 1 3 -2
1 1 5 0

10
9

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

[1, i] 를 구 하 는 것 과 잊 지 마 세 요 * (i + 1)
4 구간 최대 치 + 단일 업데이트 (단일 지점 직접 수정)
이 응용 은 사실 위의 구 화 와 는 다 릅 니 다. c [i] 는 현재 관할 구간 의 최대 치 를 나타 내 고 있 습 니 다. a [i] 는 원래 의 배열 을 대표 하기 때문에 c [i]수정 할 때 는 그 가 관할 하 는 구간 내의 모든 값 을 순서대로 비교 하면 관할 하 는 구간 안의 최대 치 를 얻 을 수 있 고, 매번 수정 할 때마다 원수 조 를 최대 치 로 삼 아 관할 구간 을 옮 겨 다 닌 다.

void init()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);//a[]    ，c[]        
        c[i]=a[i];//c[i]   i            
        // i=8，        7，6，4，      
        for(j=1; j

위 는 입력 함수 이 고, 다음은 단일 업데이트 함수 입 니 다.

void update(int x,int val)
{
    int i,j;
    a[x]=val;
    for(i=x; i<=n; i+=lowbit(i)) //       ，              
    {
        c[i]=a[i];//          
        //     c[] ，                      
        for(j=1; j

구간 에서 가장 값 을 구 하 는 함 수 는 천천히 이해 해 야 한다. c [r] 가 반드시 [l, r] 의 최대 치 는 아니다. [1, l - 1] 의 최대 치 를 포함 할 수 있 기 때문에 처음에 최대 치 는 a [r] 였 다가 옮 겨 다 니 기 시작 한 다음 에 r - 1, r - lowbit (r) > = l 이 관할 구간 에 있다 는 것 을 증명 하면 업데이트 할 수 있다.

int query(int l,int r)
{
    int ans=a[r];//  l==r,      a[r]
    while(l!=r)
    {
        for(r-=1; r-lowbit(r)>=l; r-=lowbit(r)) //r-lowbit(r)=l
        //       a[r]   ，    c[r]          
    }
    return ans;
}

이상 은 hdu 1754 의 코드 이 고 poj 3264 의 가장 값 이 떨 어 지 는 것 도 마찬가지 로 구 할 수 있 습 니 다. m [] 배열 을 추가 하여 최소 치 를 표시 한 다음 에 c [] 의 조작 과 같 으 면 됩 니 다.
5. k 작은 값 구하 기
같은 문제 에 대해 서 는 k 의 큰 값, 즉 n + 1 - k 가 작 으 면 똑 같이 처리 하면 됩 니 다. 사실은 2 분 의 접근 방법 을 이용 하여 구 하 는 것 입 니 다. 이전의 getsum (x) 함수 와 비슷 하지만 여 기 는 2 진법 의 가장 큰 자리 부터 옮 겨 다 니 고 있 습 니 다. 그 사실 을 고려 해 보 세 요. getsum (x) 의 가장 큰 관할 구간 도 2 ^ k 입 니 다.

int Find_kth(int k)
{
    int ans=0,cnt=0,i;
    for(i=20;i>=0;i--)
    {
        ans+=(1<=maxn||cnt+c[ans]>=k)
        {
            ans-=(1<

그래서 ans + = 1 < = k, 이것 은 이 수가 k 위 보다 크다 는 것 을 증명 하기 때문에 구간 을 축소 합 니 다.함 수 는 i 라 는 수치 가 몇 개 라 는 뜻 이 므 로 i 라 는 숫자 가 있 으 면 바로 update (i, 1) 하면 됩 니 다. 업데이트 함 수 는 최초 버 전과 같 습 니 다. 다음 문 제 는 poj 2985 와 집합 + 트 리 배열 입 니 다. update (1, n) 를 초기 화하 여 1 이라는 값 이 n 개 라 는 것 을 증명 합 니 다. 합병 할 때 a [x], a [y] 를 각각 하나 줄 입 니 다.   a [x] + a [y] 하 나 를 추가 합 니 다. 사실은 a [i] 배열 은 집합 안의 요소 의 개 수 를 찾 는 것 입 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 

이상 은 나무 모양 배열 의 간단 한 응용 이 고 각종 2 차원 나무 모양 배열 이 있 으 니 나중에 업데이트 하 세 요.