/* FILE: dynArrayTrivial.cpp last change: 23-Jan-2013 author: Romeo Rizzi * the trivial (and slow) solver for problem dynArray */ #define NDEBUG // NDEBUG definita nella versione che consegno #include #ifndef NDEBUG # include // uso di cin e cout non consentito in versione finale #endif #include using namespace std; const int MAX_N = 1000000; // massima dimensione dell'array A int n; // effettiva dimensione dell'array A int A[MAX_N +1]; int m; // numero di istruzioni in input int slowSumOverA(int posA, int posB) { // only for comparison int sum = 0; while( posA <= posB ) sum += A[posA++]; return sum; } int prefixSumA[MAX_N +1]; // prefixSumA[i] = A[1] + A[2] + ... + A[i] // to be updated only before a query immidiately following an update bool updated = false; void updateSums() { updated = true; prefixSumA[0] = 0; for(int i = 1; i <= n; i++) prefixSumA[i] = prefixSumA[i-1] + A[i]; } int sumOverA(int posA, int posB) { if( !updated ) updateSums(); return prefixSumA[posB] - prefixSumA[posA -1]; } int main() { ifstream fin("input.txt"); assert( fin ); fin >> n >> m; for(int i = 1; i <= n; i++) A[i] = 0; ofstream fout("output.txt"); assert( fout ); for(int i = 0; i < m; i++) { int key, a, b; fin >> key; if( key ) { fin >> a; A[a] += key; updated = false; } else { fin >> a >> b; assert( sumOverA(a,b) == slowSumOverA(a,b) ); fout << sumOverA(a,b) << endl; } } fin.close(); fout.close(); return 0; }