'고급' 데이터 구조 - 트 리 배열!

전환 하 다  https://www.cnblogs.com/RabbitHu/p/BIT.html
1. 단점 수정 + 구간 조회
가장 간단 한 트 리 배열 은 다음 과 같다.

void add(int p, int x){ //   p  x
    while(p <= n) sum[p] += x, p += p & -p;
}
int ask(int p){ //   p    
    int res = 0;
    while(p) res += sum[p], p -= p & -p;
    return res;
}
int range_ask(int l, int r){ //    
    return ask(r) - ask(l - 1);
}

2. 구간 수정 + 단일 조회
'차이 점' (배열 의 모든 요소 와 이전 요소 의 차 이 를 기록 하 는 것) 을 통 해 이 문 제 를 문제 1 로 바 꿀 수 있다.
조회 하 다.
원래 의 배열 을 a [i] 로 설정 하고 배열 d [i] = a [i] - a [i - 1] (a [0] = 0) 를 설정 하면 a [i] = ＞ ij = 1d [j] 를 설정 하여 d [i] 의 접두사 와 조 회 를 구 할 수 있다.
수정 하 다.
구간 [l, r] 에 x 를 더 했 을 때 a [l] 와 이전 원소 a [l - 1] 의 차 이 는 x, a [r + 1] 과 a [r] 의 차 이 는 x 감소 했다.d [i] 배열 의 정의 에 따라 a [l] 에 x 를 더 하고 a [r + 1] 에 x 를 빼 면 됩 니 다.

void add(int p, int x){ //                
    while(p <= n) sum[p] += x, p += p & -p;
}
void range_add(int l, int r, int x){ //   [l, r]  x
    add(l, x), add(r + 1, -x);
}
int ask(int p){ //    
    int res = 0;
    while(p) res += sum[p], p -= p & -p;
    return res;
}

3. 구간 수정 + 구간 조회
이것 은 가장 자주 사용 하 는 부분 이자 선분 나무 로 가장 번 거 로 운 부분 을 쓰 고 있 습 니 다. 하지만 지금 우 리 는 나무 모양 의 배열 이 생 겼 습 니 다!
어떻게 빌 지?우 리 는 문제 2 의 '차이 점' 방향 을 바탕 으로 문제 2 가 구축 한 트 리 배열 에서 접두사 와:
위치 p 의 접두사 와 = ∑ i = 1pa [i] = ∑ i = 1p ∑ j = 1id [j] 는 등식 의 가장 오른쪽 식 ∑ pi = 1 ∑ ij = 1d [j] 에서 d [1] 는 p 회, d [2] 는 p - 1 로 사용 되 었 다
다음....................................................................................
그러면 우 리 는 두 배열 의 접두사 와: 한 배열 은 sum 1 [i] = d [i] 이 고 다른 배열 은 sum 2 [i] = d [i] 입 니 다.
조회 하 다.
위치 p 의 접두사 와 즉: (p + 1) * sum 1 배열 의 p 접두사 와 - sum 2 배열 의 p 접두사 와.
구간 [l, r] 의 합: 위치 r 의 접두사 와 - 위치 l 의 접두사 와.
수정 하 다.
sum 1 배열 의 수정 과 같은 문제 2 에서 d 배열 의 수정.
sum 2 배열 의 수정 도 비슷 합 니 다. 우 리 는 sum 2 [l] 에 l * x 를 더 하여 sum 2 [r + 1] 에 (r + 1) * x 를 빼 줍 니 다.

void add(ll p, ll x){
    for(int i = p; i <= n; i += i & -i)
        sum1[i] += x, sum2[i] += x * p;
}
void range_add(ll l, ll r, ll x){
    add(l, x), add(r + 1, -x);
}
ll ask(ll p){
    ll res = 0;
    for(int i = p; i; i -= i & -i)
        res += (p + 1) * sum1[i] - sum2[i];
    return res;
}
ll range_ask(ll l, ll r){
    return ask(r) - ask(l - 1);
}

이 구간 으로 구간 구 화 문 제 를 수정 하 는 것 은 시간 적 으로 나 공간 적 으로 나 레이 지 표 시 된 선분 트 리 보다 우수 하 다.
 
 
다른 사내 로 전향 하 다https://blog.csdn.net/zars19/article/details/54620021
단점 수정 구간 조회

#include
#include
#include
#include
using namespace std;
int n,m;
int c[500005];
int lowbit(int x)
{
    return (-x)&x;
}
void add(int pos,int x)
{
    while(pos<=n)
    {
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
void input()
{
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
}
int query(int pos)
{
    int res=0;
    while(pos>0)
    {
        res+=c[pos];
        pos-=lowbit(pos);
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    input();
    int f,x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&f,&x,&y);
        if(f==1)
        add(x,y);
        else if(f==2)
        cout<

구간 수정 단점 조회

#include
#include
#include
#include
using namespace std;
int c[500005];
int n,m;
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int x)
{
    while(pos<=n)
    {
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
int query(int pos)
{
    int res=0;
    while(pos>0)
    {
        res+=c[pos];
        pos-=lowbit(pos);
    }
    return res;
 } 
int main()
{
    scanf("%d%d",&n,&m);
    int x=0,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y);
        add(i,y-x);
        x=y;
    }
    int opt,k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(x,k);
            add(y+1,-k);
        }
        else if(opt==2)
        {
            scanf("%d",&x);
            printf("%d
",query(x));
        }
    }
    return 0;
 } 

구간 수정 구간 조회 *
여기 서 원수 조 a 를 간략하게 설명 하고 차분 수 조 d 는 an = ∑ i = 1ndi 가 있 기 때문에 ∑ i = 1nai = ∑ i = 1n ∑ j = 1idj = ∑ i = 1n (n − i + 1)×di=(n+1)×∑i=1ndi−∑i=1ndi×i
그래서 우 리 는 두 개의 트 리 배열, c1 저장 di, c2 저장 di 를 유지 합 니 다.×i

#include
#include
#include
using namespace std;
long long c[200005][2];
int n,q;
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int x,int f)
{
    while(pos<=n)
    {
        c[pos][f]+=x;
        pos+=lowbit(pos);
    }
}
long long query(int pos,int f)
{
    long long res=0;
    while(pos>0)
    {
        res+=c[pos][f];
        pos-=lowbit(pos);
    }
    return res;
 }
long long ask(int pos)
{
    long long res=(pos+1)*query(pos,0)-query(pos,1);
    return res; 
}
int main()
{
    scanf("%d",&n);
    int a=0,b,opt,x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b);
        add(i,b-a,0);
        add(i,(b-a)*i,1);
        a=b;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&a,&b,&x);
            add(a,x,0);
            add(b+1,-x,0);
            add(a,x*a,1);
            add(b+1,-x*(b+1),1);
        }
        else if(opt==2)
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",ask(b)-ask(a-1));
        }
    }
    return 0;
}