Hello, i tried to solve impossible boss problem, but i failed in stage, i dont know why.
#include <iostream>
#include <cmath>
typedef unsigned int UINT;
void update(UINT * SegTree, UINT size){
for (int i = size-1; i >= 0; i–){
SegTree[i] = SegTree[(i<<1)+1] + SegTree[(i<<1)+2];
}
}
UINT find(UINT * SegTree, UINT curr, UINT start, UINT end, UINT qleft, UINT qright){
if (qleft == start && qright == end) {
return SegTree[curr];
}
UINT left = 2curr + 1;
UINT right = 2curr + 2;
UINT mid = (start + end)/2;
if (qright <= mid){
return find(SegTree, left, start, mid, qleft, qright);
} else if (qleft > mid) {
return find(SegTree, right, mid+1, end, qleft, qright);
}
return find(SegTree, left, start, mid, qleft, mid) + find(SegTree, right, mid+1, end, mid+1, qright);
}
int main(int argc, char const *argv[]) {
UINT N, Q, exp = 0, op, en, st;
std::cin >> N >> Q;
while(std::pow(2, exp) < (2*N -1)) exp++;
UINT leaves = std::pow(2, (exp-1));
UINT MaxSize = std::pow(2, exp) -1;
UINT SegTree[MaxSize] = { 0 };
for (UINT i = 0; i < Q; i++) {
std::cin >> op >> en >> st;
if(op){
std::cout << find(SegTree, 0, 0, leaves-1, en-1, st-1) << ‘\n’;
}
else{
UINT counter = 0;
for(UINT j = en-1; j < st; j++){
counter++;
SegTree[MaxSize - leaves + j] += counter;
}
update(SegTree, MaxSize - leaves);
}
}
return 0;
}