数据结构--树状数组 - HelloWorld开发者社区

Feature

To deal with dynamic continuous and query problem, and for a given array: $A_1, A_2, \dotsc A_n$, we're asked to support these two operations:

let $A_x$ increase $d$
calculate $A_L+A_{L+ 1}+\dotsc +A_R$

To make our algorithm cost less time, we introduce (Binary Indexed Tree, BIT). Before we introduce the concept of the BIT, we need to discuss lowbit

Lowbit

It's the number that is represented by the rightmost "1".

Property

If $i$ is left child, then it's father's index is $i+lowbit(i)$, and right child is correspond to $i-lowbit(i)$.

If we set the nodes by set the same lowbit of their index at the same height layer, we can gain a beautiful binary tree.

数据结构--树状数组

Calculate Lowbit With Bit-operation

$lowbit(x)= x\& -x$

Important Auxiliary Array

$C_i= A_{i-lowbit(i)+1}+A_{i-lowbit(i)}+\dotsc +A_i$

Take picture lowbit tree 2 for example$C_i$ represents the sum of the red line which contains the index $i$. For example, $C_{12}$ is the sum of the red line, and this red line contain $A_9, A_{10}, A_{11}, A_{12}$.

Use $C_i$ Calculate The Sum Of Prefix

"Climb the tree". Here are the rules.

Begin from the end of the prefix sum.
Find the higher node which has smaller index.
Find the nearest node which satisfy the second rules.
Sum the $C_i$ up along the way you climb.

Update $C_i$ If Some $A_j$ Changes

"Climb the tree". Here are the rules.

Begin from the changed point.
Find the higher node which has bigger index.
Stop at the highest node of the current BIT.
Change the $C_i$ you met along the way you climb.

Code

int C[MAX_N+1], n;       //n represent the length of A
int Sum(int i)
{
    int s= 0;
    while (i> 0){
        s+= C[i];
        i-= i& -i;
    }
    return s;
}
void Add(int i, int x)
{
    while(i<= n){
        C[i]+= x;
        i+= i&-i;
    }
}

2-D BIT

The second dimension is a bit whose nodes' element is also a BIT.

OJ Practise

POJ 1656

My first code, it's still use the idea of 1-D BIT and it doesn't have a high efficiency.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int wd= 101;

int bo[wd][wd];
int C[wd][wd];

inline int Lowbit(int x){
    return x & (-x);
}
int Sum(int x, int y)   //(x, y)
{
    int s= 0;
    while (y>0){
        s+= C[x][y];
        y-= Lowbit(y);
    }

    return s;
}
void Add(int x, int y, int d)
{
    while (y< wd){
        C[x][y]+= d;
        y+= Lowbit(y);
    }
}
void BUpdate(int x, int y, int L)
{
    for (int i= x; i<x+L; ++i){
        for (int j= y; j<y+L; ++j){
            if (!bo[i][j]){
                bo[i][j]= 1;
                Add(i, j, 1);
            }
        }
    }
}
void WUpdate(int x, int y, int L)
{
    for (int i= x; i<x+L; ++i){
        for (int j= y; j<y+L; ++j){
            if (bo[i][j]){
                bo[i][j]= 0;
                Add(i, j, -1);
            }
        }
    }
}
int Answer(int x, int y, int L)
{
    int s= 0;

    for (int i= x; i<x+L; ++i){
        s+= (Sum(i, y+L-1)- Sum(i, y-1));
    }
    printf("%d\n", s);

    return s;

}

int main()
{
    int t, x, y, L;
    char cd[7];
    scanf("%d", &t);
    memset(bo, 0, wd*wd*sizeof(int));
    memset(C, 0, wd*wd*sizeof(int));

    while (t--){
        scanf("%s %d %d %d", cd, &x, &y, &L);

        switch(cd[0]){
            case 'W':
                WUpdate(x, y, L);
                break;
            case 'B':
                BUpdate(x, y, L);
                break;
            case 'T':
                Answer(x, y, L);
                break;
            default:
                break;
        }
    }
    return 0;
}

This has $O( \log (N) \times \log (W))$ time. $N\& W$ is the length and the width of the rectangle.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int wd= 101;

int bo[wd][wd];
int C[wd][wd];

inline int Lowbit(int x){
    return x & (-x);
}
int Sum(int x, int y)   //(x, y)
{
    int s= 0, tpy;
    while (x>0){
        tpy= y;
        while (tpy>0){
            s+= C[x][tpy];
            tpy-= Lowbit(tpy);
        }
        x-= Lowbit(x);
    }

    return s;
}
void Add(int x, int y, int d)
{
    int tpy;
    while (x<wd){
        tpy= y;
        while (tpy< wd){
            C[x][tpy]+= d;
            tpy+= Lowbit(tpy);
        }
        x+= Lowbit(x);
    }
}
void BUpdate(int x, int y, int L)
{
    for (int i= x; i<x+L; ++i){
        for (int j= y; j<y+L; ++j){
            if (!bo[i][j]){
                bo[i][j]= 1;
                Add(i, j, 1);
            }
        }
    }
}
void WUpdate(int x, int y, int L)
{
    for (int i= x; i<x+L; ++i){
        for (int j= y; j<y+L; ++j){
            if (bo[i][j]){
                bo[i][j]= 0;
                Add(i, j, -1);
            }
        }
    }
}
int Answer(int x, int y, int L)
{
    int s= 0;

    s= Sum(x+L-1, y+L-1)+Sum(x-1, y-1)-Sum(x+L-1, y-1)-Sum(x-1, y+L-1);
    printf("%d\n", s);

    return s;

}

int main()
{
    int t, x, y, L;
    char cd[7];
    scanf("%d", &t);
    memset(bo, 0, wd*wd*sizeof(int));
    memset(C, 0, wd*wd*sizeof(int));

    while (t--){
        scanf("%s %d %d %d", cd, &x, &y, &L);

        switch(cd[0]){
            case 'W':
                WUpdate(x, y, L);
                break;
            case 'B':
                BUpdate(x, y, L);
                break;
            case 'T':
                Answer(x, y, L);
                break;
            default:
                break;
        }
    }
    return 0;
}