[codevs 1080] 선분 수 연습 의 꽃 해법

선분 트 리 템 플 릿 문제
먼저 폭력 을 행사 하 다

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100000 + 5;
int num[MAXN];
int n,m,q,a,b;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&num[i]);
    for(int i = 1;i <= n;i ++)
        num[i] += num[i - 1];
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d",&q,&a,&b);
        if(q == 1)
            for(int i = a;i <= n;i ++)
                num[i] += b;
        else
            printf("%d
",num[b] - num[a - 1]);
    }
    return 0;
}

됐어. 아까 는 아니 야.
크 크................................................................

#include
#include
#define ll long long
using namespace std;
int num[200010];
struct dc{
    int l,r;
    ll sum,add;
}tree[200010*4];

void build(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r)
    {
        tree[p].sum=num[l];
        return ;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

void spread(int p)
{
    if(tree[p].add)
    {
        tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);
        tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);
        tree[p*2].add+=tree[p].add;
        tree[p*2+1].add+=tree[p].add;
        tree[p].add=0;
    }
}

void change(int p,int a,int x)
{
    if(a==tree[p].l&&tree[p].r==a)
    {
        tree[p].sum+=x;
        tree[p].add+=x;
        return;
    }
    spread(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(a<=mid) change(p*2,a,x);
    if(mid*2+1,a,x);
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
ll ask(int p,int l,int r)
{
if(l<=tree[p].l&&tree[p].r<=r)
{
return tree[p].sum;
}
spread(p);
int mid=(tree[p].l+tree[p].r)/2;
ll ans=0;
if(l<=mid) ans+=ask(p*2,l,r);
if(mid*2+1,l,r);
return ans;
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
build(1,1,n);
int S;scanf("%d",&S);
while(S--)
{
int s;scanf("%d",&s);
int a,b,x;
if(s==1)
{
scanf("%d%d",&a,&x);
change(1,a,x);
}
else
{
scanf("%d%d",&a,&b);
printf("%lld",ask(1,a,b));
}
}
return 0;
}

응, 이게 바로 선분 나무 야.
그리고 두 번 째 는...............................................................

#include 
#include 
using namespace std;
const int MAXN = 100000 + 5;
int n,z,a,b,tree[MAXN];
int lowbit(int x)
{
    return x & (- x);
}
void add(int x,int y)
{
    while(x <= n)
    {
        tree[x] += y;
        x += lowbit(x);
    }
    return;
}
int qzh(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
int answer(int s,int t)
{
    return qzh(t) - qzh(s - 1);
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&z);
        add(i,z);
    }
    int m;
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&z);
        if(z == 1)
        {
            scanf("%d %d",&a,&b);
            add(a,b);
        }
        else
        {
            scanf("%d %d",&a,&b);
            printf("%d
",answer(a,b));
        }
    }
    return 0;
}

응, 이게 BIT 야.
그리고 내 가 가장 좋아 하 는, zkw 라인 트 리!

#include 
#include 
#include 
using namespace std;

const int MAXN = 1000000 + 5;
const int MAXM = 10000 + 5;
int treee[MAXN],M;
void init(int n)
{
    M = 1 << ((int)log2(n + 1) + 1);
    for(int i = M + 1; i <= M + n; i++)
        cin >> treee[i];
    for(int i = M - 1; i >= 1; i--)
        treee[i] = treee[i << 1] + treee[i << 1 | 1];

}
void add(int x,int a)
{
    for(treee[x += M] += a,x >>= 1;x;x >>= 1)
    {
         treee[x] = treee[x << 1] + treee[x << 1 | 1];
    }
    return;
}
int answer(int s,int t)
{
    int ans = 0;
    for(s = s + M - 1,t = t + M + 1;s ^ t ^ 1;s >>= 1,t >>= 1)
    {
        if(~s & 1) ans += treee[s ^ 1];
        if(t & 1) ans += treee[t ^ 1];
    }
    return ans;
}
int n,m,q,a,b;
int main()
{
    cin >> n;
    init(n);
    cin >> m;
    for(int i = 1;i <= m;i ++)
    {
        cin >> q >> a >> b;
        if(q == 1)
        {
            add(a,b);
        }
        if(q == 2)
        {
            cout << answer(a,b) << endl;
        }
    }
    return 0;
}

zkw 너무 강해...
그리고... 그리고... 바로 오늘 의 메 인 splay 입 니 다.

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100000 + 5;
struct tr
{
    tr *ch[2],*f;
    int val,sz,cnt;
    bool dir()
    {
        return f -> ch[1] == this;
    }
    void maintain()
    {
        cnt = ch[0] -> cnt + ch[1] -> cnt + val;
        sz = ch[0] -> sz + ch[1] -> sz + 1;
    }
    void setc(tr *x,int v)
    {
        (ch[v] = x) -> f = this;
    }
}tree[MAXN],*root,*null;
int tot;
tr* newdot(int v,tr *f)
{
    tr *p = tree + tot++;
    p -> val = p -> cnt = v;
    p -> sz = 1;
    p -> ch[0] = p -> ch[1] = null;
    p -> f = f;
    return p;
}
void init()
{
    tot = 0;
    null = newdot(0,null);
    null -> sz = 0;
    root = null;
    return;
}
void rot(tr *x)
{
    tr *p = x -> f;
    int d = x -> dir();
    p -> f -> setc(x,p -> dir());
    p -> setc(x -> ch[d ^ 1],d);
    p -> maintain();
    x -> setc(p,d ^ 1);
    if(root == p)
        root = x;
    return;
}
void splay(tr *x,tr *to = null)
{
    while(x -> f != to)
        if(x -> f -> f == to)
            rot(x);
        else
            x -> dir() == x -> f -> dir() ? (rot(x -> f),rot(x)) : (rot(x),rot(x));
    return;
}
void add(int p,int v)
{
    tr *x = root;
    while(true)
    {
        x -> cnt += v;
        if(x -> ch[0] -> sz + 1 == p)
        {
            x -> val += v;
            break;
        }
        int d = x -> ch[0] -> sz + 1 <= p;
        if(d)
            p -= x -> ch[0] -> sz + 1;
        x = x -> ch[d];
    }
    splay(x);
    return;
}
int sum(int xx,int yy)
{
    int p = xx - 1;
    tr *x = root;
    while(true)
    {
        int d = x -> ch[0] -> sz + 1 <= p;
        if(x -> ch[0] -> sz + 1 == p)
            break;
        if(d)
            p -= x -> ch[0] -> sz + 1;
        x = x -> ch[d];
    }
    splay(x);
    p = yy + 1;
    while(true)
    {
        int d = x -> ch[0] -> sz + 1 <= p;
        if(x -> ch[0] -> sz + 1 == p)
            break;
        if(d)
            p -= x -> ch[0] -> sz + 1;
        x = x -> ch[d];
    }
    splay(x,root);
    return x -> ch[0] -> cnt;
}
int num[MAXN];
void build(int l,int r,tr * &x,tr *f)
{
    if(l > r)return;
    int mid = (l + r) >> 1;
    x = newdot(num[mid],f);
    build(l,mid - 1,x -> ch[0],x);
    build(mid + 1,r,x -> ch[1],x);
    x -> maintain();
    return;
}
int n,m,q,a,b;
int main()
{
    init();
    scanf("%d",&n);
    for(int i = 2;i <= n + 1;i ++)
        scanf("%d",&num[i]);
    build(1,n + 2,root,null);
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d",&q,&a,&b);
        if(q == 1)
            add(a + 1,b);
        else
            printf("%d
",sum(a + 1,b + 1));
    }
    return 0;
}

그래, 이게 바로 splay...
이후 의 보충 으로 블록 에 관 한 부분 을 나 누 어 30 분 동안 조련 한 경험 은?

번 호 는 0 부터

아웃 판단 잊 지 마 세 요

언제든지 l < r

sqrt……

코드

#include 
#include 
#include 
#include 
#include 
#define KILL puts("haha")
using namespace std;

const int MAXN = 100000 + 5;
int sum[MAXN],num[MAXN];
int n,m;
int M;
void init()
{
    M = sqrt(n) + 1;
    for(int i = 0;i < n;i ++)
        if(i % M == 0)
            sum[i / M] = num[i];
        else
            sum[i / M] += num[i];
    return;
}
void change(int x,int y)
{
    num[x] += y;
    sum[x / M] += y;
    return;
}
int sumer(int x,int y)
{
    int ans = 0;
    while(x % M && x < y)//       
        ans += num[x++];
    while(y % M && y > x)
        ans += num[y--];
    ans += num[y];//      ……
    while(x < y)
        ans += sum[x / M],x += M;
    return ans;
}
int q,a,b;
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i ++)
        scanf("%d",&num[i]);
    init();
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d",&q,&a,&b);
        if(q == 1)
            change(a-1,b);
        else
            printf("%d
",sumer(a-1,b-1));
    }
    return 0;
}

요컨대 이렇다. 틀 문제 하나 도 할 말 이 없 는데.....................................................