The original tree array can be so simple?

author | Small K

Produce | official account ： Small K Algorithm （ID：xiaok365）

01

Origin story

Yes N The numbers are arranged in a row , How to quickly modify and sum intervals ？

02

analysis

The easiest way to think of first is to find the prefix and sum[i], And then the interval [a,b] The sum of can be directly passed through sum[b]-sum[a-1] obtain .

But if you want to modify the array , There will be some problems . For example, yes. a[3] Add 1, Then the following corresponding sum[3],sum[4],sum[5] All need to be modified , This efficiency is very low .

The reason lies in sum[i] Is the front section [1,i] The sum of all elements in , So modify any element , Then the back sum[i] Have to recalculate .

Can we find a discontinuous prefix and , You only need to count some elements in the previous interval . In this way, you are modifying a a[i] Will not affect all the following sum[i].

In fact, it is necessary to find such a mapping relationship , Both the prefix and , It can also improve the efficiency of modification .sum[i] It used to be a statistical interval [1,i] be-all i Elements , Now it's a statistical interval [1,i] Medium k Elements .

The tree array is actually such a mapping .

03

Definition

The tree array calculates the sum of the previous elements according to the following correspondence , But the law may not be seen directly .

First put the subscript of the element 1、2、3... Convert to binary .

Then put each binary number , From right to left , Intercept to the first 1 The location of . The intercepted binary number will also correspond to a decimal number .

such as 12 The corresponding binary number is 1100, The binary number intercepted is 100, and 100 Convert decimal to zero 4. So we can define such an operation ,lowbit(12)=4.

So this one lowbit How to calculate quickly ？

Computer principle , First of all, we know that there is the original code , Inverse code , Complement code . The highest bit is the sign bit ,0 Is a positive number ,1 It's a negative number . Three positive numbers are the same , The inverse of a negative number is a sign bit invariant , The rest of the bits are reversed , The complement is the inverse plus 1. In a computer, negative numbers are stored as complements .

And then look at the following 12 and -12, When complement performs bit and operation , Exactly lowbit operation .

Code implementation ：

int lowbit(int x) {
    return x & -x;
}

Copy

Put the corresponding position above lowbit All calculated and observed , You can find lowbit The value of is exactly sum[i] Count the number of elements .

The general rules are summarized as follows ： sum[i] Equal to interval [i-lowbit(i)+1,i] The sum of all elements in . That is, from the position i Start , Forward count lowbit(i) Elements , Add up to sum[i].

04

law

lowbit(i) The corresponding number must be 1,2,4..., Because the intercepted binary is 1000.... according to lowbit(i) You can do it first sum[i] Layering .

and sum[i] Elements also have an inclusion relationship , Then bring up the inclusion relation .

sum[i] It is the continuous lowbit(i) The sum of the elements , Direct expansion is clearer . The red rectangle is the sum of the small blue squares covered below .

Red is sum Array , Blue is a Array , Then observe the relationship between subscripts .

05

Single point modification

For example, modify a[2], because sum[2],sum[4] It's all about a[2], Therefore, the corresponding must be modified .

If modified a[3], because sum[3],sum[4] It's all about a[3], Therefore, the corresponding must be modified .

Observation found that , Modify an element a[i] when ,sum[i] It is a layer by layer upward modification , The subscript of the previous layer is exactly the subscript of the current layer i add lowbit(i).

Code implementation ：

void add(int index, int x) {
    while (index <= n) {
        sum[index] += x;
        index += lowbit(index);
    }
}

Copy

06

Interval query

For example, query interval [1,5], Statistics are needed sum[5],sum[4].

If the query interval [1,3], Statistics are needed sum[3],sum[2].

Observation found that , Query range [1,i] The prefix and hour of , It is a forward query paragraph by paragraph , The subscript of the next segment is exactly the subscript of the current segment i subtract lowbit(i).

Code implementation ：

int query(int index) {
    int ret = 0;
    while (index > 0) {
        ret += sum[index];
        index -= lowbit(index);
    }
    return ret;
}

Copy

such , You can easily handle single point modification and interval query , But the first problem is interval modification , How to realize this ？

07

Interval modification

First we have to introduce a difference array d[i],d[i]=a[i]-a[i-1].

An array d[i] Calculate the prefix and , It can also be restored to the original array elements a[i].

Replace by formula , Prefix and of the original array sum[i] It can also be done through d[i] To get .

This is how it unfolds .

Through observation , The above formula can be modified as follows . The most important one is sigma(d[j]) and sigma(d[j]*j).

If maintenance d[i] and d[i]*i Prefixes of two arrays and , You can quickly get sum[k].

When it comes to interval [3,5] increase 2 when , because d[i] It's a differential array , So just d[3] increase 2, Yes d[6] subtract 2 that will do . Empathy e[i] Array , It only needs e[3] increase 2*3, Yes e[6] subtract 2*6.

The general rule is as follows ：

Code implementation ：

#define LL long long

//  Single modification 
void add(LL *sum, LL index, LL x) {
    while (index <= n) {
        sum[index] += x;
        index += lowbit(index);
    }
}

//  Interval modification 
void range_add(LL left, LL right, LL x) {
    right++;
    add(sum1, left, x);
    add(sum1, right, -x);
    add(sum2, left, x * left);
    add(sum2, right, -x * right);
}

Copy

08

Interval query

Code implementation ：

//  Single query 
LL query(const LL *sum, LL index) {
    LL ret = 0;
    while (index > 0) {
        ret += sum[index];
        index -= lowbit(index);
    }
    return ret;
}

//  Interval query 
LL range_query(LL left, LL right) {
    left--;
    LL sumA = (left + 1) * query(sum1, left) - query(sum2, left);
    LL sumB = (right + 1) * query(sum1, right) - query(sum2, right);
    return sumB - sumA;
}

Copy

09

summary

Tree arrays are mainly used for interval operations , Compared with the segment tree , The code implementation is too simple , And it's very efficient , Well worth studying and mastering .

The original author of this article ： Small K, A writer with unique thinking .