Playground
#include <iostream> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int MAX_5N = 500001; int tree[MAX_5N]; void update(int pos, int value, int interval_index, int interval_left, int interval_right) { //momentno gledame vo tree[interval_index], //shto go sodrzhi intervalot [interval_left...interval_right] if (interval_left > pos || interval_right < pos || interval_left > interval_right) { //intervalot e celosno levo ili desno od pozicijata (pos) koja sakame da ja azurirame return ; } if (interval_left == interval_right) { //dojdovme do poslednoto nivo vo drvoto, pa azuriraj ja vrednosta if (interval_left == pos) { tree[interval_index] = value; } return ; } //inaku, rekurzivno azuriraj ja levata i desnata polovina od intervalot int middle = (interval_left + interval_right) / 2; update(pos, value, (2 * interval_index), interval_left, middle); update(pos, value, (2 * interval_index + 1), middle+1, interval_right); //od koga kje zavrshime so rekurzijata, zbirot kaj sekoe teme e zbir od negovite deca tree[interval_index] = (tree[2 * interval_index] + tree[2 * interval_index + 1]); } int query(int from, int to, int interval_index, int interval_left, int interval_right) { //momentno gledame vo tree[interval_index], //shto go sodrzhi intervalot [interval_left...interval_right] if (interval_left > to || interval_right < from || interval_left > interval_right) { //intervalot e celosno levo ili desno od opsegot za koj sakame da presmetame suma return 0; } if (from <= interval_left && interval_right <= to) { //intervalot e celosno vo opsegot za koj sakame da presmetame suma, pa dodadi go return tree[interval_index]; } int middle = (interval_left + interval_right) / 2; int sum_left = query(from, to, (2 * interval_index), interval_left, middle); int sum_right = query(from, to, (2 * interval_index + 1), middle+1, interval_right); return (sum_left + sum_right); } int main() { int n = 1000; memset(tree, 0, sizeof(tree)); for (int i=0; i<1500; i++) { if (i%2 == 0) { //napravi azuriranje na vrednosta kaj "indeks" int index = rand() % n; int value = rand() % 79103; update(index, value, 1, 0, n-1); } else { //presmetaj ja sumata na posledovatelni vrednosti int number1 = rand() % n; int number2 = rand() % n; int from = min(number1, number2); int to = max(number1, number2); int sum = query(from, to, 1, 0, n-1); cout << "sum of elements in the interval [" << from << "," << to << "] is: " << sum << endl; } } return 0; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!