https://www.codechef.com/START5C/problems/CHEFQUER
This problem appeared in June CODECHEF Starters 2021. I loved the idea of the solution . I wasn’t aware of Fenwick trees before and I’m glad that I got to learn a new Data Structure but I couldn’t understand some part of the editorial. Please help me by clarifying my doubts.
Editorial Link: https://discuss.codechef.com/t/chefquer-editorial/91667
In Editorialist’s solution I couldn’t understand the range_add function.
void add(int idx, int val) {
for (++idx; idx < n; idx += idx & -idx)
bit[idx] += val;
}
void range_add(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
I thought we should val to all the indices from L to R(I know doing this is costly) but in the range_add function they added val to L and subtracted val at r + 1. Can anyone explain me why are we doing this?