ZKW 라인 트 리 에 보급!

아, 지금 선분 나무 피곤 하 세 요?
너무 약해, 다시 돌아 와!
 
그럼 우 리 는 또 다른 신기 한 선분 나 무 를 즐겁게 공부 합 시다!안개
그 는 zkw 선분 수 라 고 부른다
 
이 데이터 구 조 는 회색 으로 쓰기 쉽다.
속도 가 빠르다.
밑 에서 위로 비 귀속 버 전의 선분 트 리 입 니 다!
 
우선 ppt 를 살 펴 보 겠 습 니 다. 이 건 발명자 의 PPT 입 니 다. (아, ppt 내 코드 가 틀 렸 습 니 다..................................................
통계 적 힘
 
그래, 우리 쓰 자 ~
우선 예비 조건:

int M,T[maxn*2+2];

M 은 무엇 을 말 하 는 것 입 니까? M 은 이 zkw 라인 트 리 의 맨 아래 에 있 는 그 점 을 말 합 니 다. 앞의 번 호 는 무엇 입 니까?
T 배열 은 바로 이 zkw 라인 트 리 의 배열 입 니 다. zkw 라인 트 리 는 이 진 트 리 가 가득 하기 때문에 두 배 만 열 면 됩 니 다 ~
이제 우리 나 무 를 세 웁 시다!
단일 업데이트, 구간 조회 및 하나의 예 로 ~

void build(int x)
{
    for(M=1;M<=n+1;M<<1);
    
    for(int i=1;i<=n;i++)
        scanf("%d",&T[i+M]);
    
    for(int i=M-1;i;i--)
        T[i]=T[i<<1]+T[i<<1|1];
}

이것 은 매우 약 한 바닥 에서 위로 갱신 되 는 나무 임 이 분명 하 다!
 
그리고 upddata 는 어떻게 쓰 죠?

void updata(int n,int val)
{
    T[n+=M]=val;//           
    for(n>>=1;n;n>>=1)
        T[n]=T[n<<1]+T[n<<1|1];
}

와, 사실은 선분 나무 와 같은 뜻 이 야. 바로 노드 를 따라 위로 올 라 가면 돼!
 
query 가 붓 나 요? 아니면 쉬 워 요.

int query(int l,int r)
{
    int ans=0;
    l=l+M-1,r=r+M+1;
    for(;l^r^1;l>>1,r>>=1)
    {
        if(~l&1)ans+=T[l^1];
        if(r&1) ans+=T[r^1];
    }
    return ans;
}

이 난잡 한 비트 연산 은 무슨 뜻 입 니까?
l ^ r ^ 1 의 뜻 은 왼쪽 의 이 점 과 오른쪽 이 점 이 서로 형제 가 되 는 지, 아니면 아예 하나의 점 이라는 것 입 니 다.
~l&1 바로 이 왼쪽 의 이것 이 왼쪽 아들 인지 아 닌 지 를 판단 하 는 것 이다. r & 1 은 이 노드 가 오른쪽 두 아들 인지 아 닌 지 를 판단 하 는 것 이다.
그렇다면 그의 형 제 를 더 해 야 겠 군 ~
아, zkw 단일 업데이트 구간 조회 가 여기까지 입 니 다.
우 리 는 먼저 예 제 를 하나 풀 자.
HDU 1166 적병 이 포진 하 다 단일 업데이트, 구간 조회

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
//const int inf=0x7fffffff;   //   
const int inf=0x3f3f3f3f;
/*

int buf[10];
inline void write(int i) {
  int p = 0;if(i == 0) p++;
  else while(i) {buf[p++] = i % 10;i /= 10;}
  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);
  printf("
");
}
*/
//**************************************************************************************
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

ll T[maxn*4];
int M,n;
void build()
{
    for(M=1;M<=n+1;M<<=1);
    for(int i=1;i<=n;i++)
        T[i+M]=read();
    for(int i=M-1;i;i--)
        T[i]=T[i<<1]+T[i<<1|1];
}

void updata(int x,int val)
{
    T[x+=M]+=val;
    for(x>>=1;x>=1;x>>=1)
    {
        T[x]=T[x<<1]+T[x<<1|1];
    }
}

ll query(int l,int r)
{
    l=l+M-1,r=r+M+1;
    ll ans=0;
    for(;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1)ans+=T[l^1];
        if(r&1) ans+=T[r^1];
    }
    return ans;
}

int main()
{
    int cas=0;
    int t=read();
    string s;
    for(int cas=1;cas<=t;cas++)
    {
        memset(T,0,sizeof(T));
        printf("Case %d:
",cas);
        n=read();
        build();
        while(cin>>s)
        {
            if(s[0]=='E')
                break;
            int a,b;
            a=read(),b=read();
            if(s[0]=='A')
                updata(a,b);
            else if(s[0]=='S')
                updata(a,-b);
            else
                printf("%lld
",query(a,b));
        }
    }
}