13. numeric array

The understanding of number - like array

Reference video ： What is sacred about tree arrays , Let's lift his veil together ！

---

Blue bridge's understanding （ Just remember the template , After that, you can not see ）

#define lowbit(x) ((x) & - (x)) 
int tree[N];
void update(int x, int d) {
       // Modifying elements a[x], a= a[x] + d
    while(x <= N) {
    
        tree[x] += d;  
        x += lowbit(x); 
    }
}
int sum(int x) {
              // Back prefix and ans = a[1] + a[2] +... + a[x]
    int ans = 0;
    while(x > 0){
    
        ans += tree[x];  
        x -= lowbit(x);
    }
    return ans;
}

introduce

The interval and problem of static array

Interval sum of dynamic arrays