Cod sursa(job #1921004)

Utilizator din99danyMatei Daniel din99dany Data 10 martie 2017 11:01:11
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
using namespace std;

#define NMAX 1005

int aint[ 5 * NMAX ];

int query ( int pos, int x, int y, int st, int dr );
void update ( int pos, int x, int st, int dr, int val );



int main () {

    int n, m, i, j, x, y, z;

    while ( 1 ) {
        scanf("%d%d%d",&x,&y,&z);
        if ( x == 1 ) update( 1, y, 1, NMAX, z );
        else printf("-->%d\n",query( 1, y, z, 1, NMAX));
    }


    return 0;

}

void update ( int pos, int x, int st, int dr, int val ) {

    if ( st == dr ) {
        aint[ pos ] += val;
        return ;
    }

    int mid = ( st + dr ) / 2;

    if ( x <= mid ) update( 2 * pos, x, st, mid, val );
    else update( 2 * pos + 1, x, mid + 1, dr, val );

    aint[ pos ] = aint[ 2 * pos ] + aint[ 2 * pos + 1 ];

}


int query ( int pos, int x, int y, int st, int dr ) {

    int mid = ( st + dr ) / 2;
    int s = 0;

    if ( x <= st && dr <= y ) return aint[ pos ];

    if ( x <= mid ) s += query ( 2 * pos, x, y, st, mid  );
    if ( mid < y ) s += query ( 2 * pos + 1, x, y, mid + 1, dr  );

    return s;

}