Binary Index Tree 树状数组 多维

BIT.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100
using namespace std;

int indextree[MAXN+1] = {};
int indexmatrix[MAXN+1][MAXN+1] = {};
//求2^k
int lowbit(int t)
{
    return t & ( t ^ ( t - 1 ) );
}

//求前n项和
int sum(int end)
{
    int sum = 0;
    while(end > 0)
    {
        sum += indextree[end];
        end -= lowbit(end);
    }
    return sum;
}

//增加某个元素的大小
void plus(int pos, int num)
{
    while(pos <= MAXN)
    {
        indextree[pos] += num;
        pos += lowbit(pos);
    }
}

//二维求(0,0)至(x,y)所有元素之和
int sum(int x, int y)
{
    int sum = 0;
    while (x > 0)
    {
        int tmpY = y;
        while (tmpY > 0)
        {
            sum += indexmatrix[x][tmpY];
            tmpY -= lowbit(tmpY);
        }
        x -= lowbit(x);
    }
    return sum;
}

//二维增加(x, y)处元素的大小
void plus(int x, int y, int num)
{
    while(x <= MAXN)
    {
        int tmpY = y;
        while (tmpY <= MAXN)
        {
            indexmatrix[x][tmpY] += num;
            tmpY += lowbit(tmpY);
        }
        x += lowbit(x);
    }
}

int main()
{
    int matrix[MAXN][MAXN] = {};

    // ATTENTION: i, j must bigger than zero. Zero will cause an error in sum() and plus().
    for (int i = 1; i < MAXN; i++)
    {
        for (int j = 1; j <MAXN; j++)
        {
            matrix[i][j] = i + j;
            plus(i, j, matrix[i][j]);
        }
    }
    while (1)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", sum(x,y));
    }

}