Cod sursa(job #280021)

Utilizator raula_sanChis Raoul raula_san Data 13 martie 2009 10:12:59
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>

#define MAX_N 100001

int S[MAX_N], T[MAX_N];
int N, M;

int Bit(int n)
{
    return
          n ^ (n & (n - 1));
}

void Update(int poz, int v)
{
     while(poz <= N)
     {
               T[poz] += v;
               poz += Bit(poz);
     }
}

int Query(int poz)
{
    int s = 0;
    while(poz > 0)
    {
              s += T[poz];
              poz -= Bit(poz);
    }
    return s;
}

int Bs(int v)
{
    -- v;
    
    int p;
    for ( p = 1; p <= N; p <<= 1 );
    
    int i;
    for ( i = 0; p; p >>= 1 )
        if(i + p <= N && Query(i+p) <= v) i += p;
        
    if(Query(i+1) == v + 1)
                  return i + 1;
    return -1;
}

int main()
{
    freopen("aib.in", "rt", stdin);
    freopen("aib.out", "wt", stdout);
    
    int i, v;
    for ( scanf("%d %d", &N, &M), i = 1; i <= N; ++i )
    {
        scanf("%d", &v);
        S[i] = S[i-1] + v;
        
        int j = i - Bit(i) + 1;
        T[i] = S[i] - S[j-1];
    }

    int a, b;
    for ( i = 1; i <= M; ++i )
    {
        scanf("%d", &v);
        
        if(v < 2)
             scanf("%d %d", &a, &b);
        else
            scanf("%d", &a);
            
        if(!v)
              Update(a, b);
        else if(v == 1)
             printf("%d\n", Query(b)-Query(a-1));
        else
            printf("%d\n", Bs(a));
    }
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}