Варианты дерева Фенвика

Одномерное дерево Фенвика

int f[MAX_SIZE];

int query(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i];
    return res;
}

void modify(int r, int val) {
    for (int i = r; i < MAX_SIZE; i |= i + 1)
        f[i] += val;
}

Запрос суммы на отрезке, изменение отдельных элементов

query(r) — сумма элементов от 0-го до r-го.

int prefixSum(int r) {
    return query(r);
}

void add(int pos, int val) {
    modify(pos, val);
}

Запрос значений отдельных элементов, изменение на отрезке

query(r) — значение r-го элемента.

int get(int pos) {
    return query(pos);
}

void add(int l, int r, int val) {
    modify(l, val);
    modify(r + 1, -val);
}

Запрос суммы на отрезке, изменение на отрезке

Tx.query(r) * r + T.query(r) — сумма элементов от 0-го до r-го.

int prefixSum(int r) {
    return Tx.query(r) * r + T.query(r);
}

void add(int l, int r, int val) {
    Tx.modify(l, val);
    Tx.modify(r + 1, -val);
    T.modify(l, val * (-l + 1));
    T.modify(r + 1, val * r);
}

Двумерное дерево Фенвика

struct BIT2D {
    vector<vector<int>> f;

    BIT2D(int h, int w) : f(h, vector<int>(w)) {}

    int query(int yr, int xr) {
        int res = 0;
        for (int y = yr; y >= 0; y = (y & (y + 1)) - 1)
            for (int x = xr; x >= 0; x = (x & (x + 1)) - 1)
                res += f[y][x];
        return res;
    }

    void modify(int y, int x, int val) {
        for (; y < f.size(); y |= y + 1)
            for (; x < f[0].size(); x |= x + 1)
                f[y][x] += val;
    }
};

Запрос суммы на прямоугольнике, изменение отдельных элементов

t.query(yr, xr) — сумма элементов от (0; 0)-го до (yr; xr)-го.

struct BIT2DRangeSumPointAdd {
    BIT2D t;

    BIT2DRangeSumPointAdd(int h, int w) : t(h, w) {}

    int sum(int yr, int xr) {
        return t.query(yr, xr);
    }

    int sum(int yl, int xl, int yr, int xr) {
        int res = sum(yr, xr);
        if (yl)
            res -= sum(yl - 1, xr);
        if (xl)
            res -= sum(yr, xl - 1);
        if (yl && xl)
            res += sum(yl - 1, xl - 1);
        return res;
    }

    void add(int y, int x, int val) {
        t.modify(y, x, val);
    }
};

Запрос значений отдельных элементов, изменение на прямоугольнике

t.query(y, x) — значение (y; x)-го элемента.

struct BIT2DPointSumRangeAdd {
    BIT2D t;

    BIT2DPointSumRangeAdd(int h, int w) : t(h, w) {}

    int get(int y, int x) {
        return t.query(y, x);
    }

    void add(int yl, int xl, int yr, int xr, int val) {
        t.modify(yl, xl, val);
        t.modify(yr + 1, xl, -val);
        t.modify(yl, xr + 1, -val);
        t.modify(yr + 1, xr + 1, val);
    }
};

Запрос суммы на прямоугольнике, изменение на прямоугольнике

tyx.query(yr, xr) * yr * xr + ty.query(yr, xr) * yr + tx.query(yr, xr) * xr + t.query(yr, xr) — сумма элементов от (0; 0)-го до (yr; xr)-го.

struct BIT2DRangeSumRangeAdd {
    BIT2D t, ty, tx, tyx;

    BIT2DRangeSumRangeAdd(int h, int w) :
        t(h, w), ty(h, w), tx(h, w), tyx(h, w) {}

    int sum(int yr, int xr) {
        int res = tyx.query(yr, xr) * yr * xr;
        res += ty.query(yr, xr) * yr;
        res += tx.query(yr, xr) * xr;
        res += t.query(yr, xr);
        return res;
    }

    int sum(int yl, int xl, int yr, int xr) {
        int res = sum(yr, xr);
        if (yl)
            res -= sum(yl - 1, xr);
        if (xl)
            res -= sum(yr, xl - 1);
        if (yl && xl)
            res += sum(yl - 1, xl - 1);
        return res;
    }

    void add(int yl, int xl, int yr, int xr, int val) {
        tyx.modify(yl, xl, val);
        tyx.modify(yr + 1, xl, -val);
        tyx.modify(yl, xr + 1, -val);
        tyx.modify(yr + 1, xr + 1, val);

        ty.modify(yl, xl, val * (-xl + 1));
        ty.modify(yr + 1, xl, -val * (-xl + 1));
        ty.modify(yl, xr + 1, val * xr);
        ty.modify(yr + 1, xr + 1, -val * xr);

        tx.modify(yl, xl, val * (-yl + 1));
        tx.modify(yr + 1, xl, val * yr);
        tx.modify(yl, xr + 1, -val * (-yl + 1));
        tx.modify(yr + 1, xr + 1, -val * yr);

        t.modify(yl, xl, val * (-xl + 1) * (-yl + 1));
        t.modify(yr + 1, xl, val * (-xl + 1) * yr);
        t.modify(yl, xr + 1, val * xr * (-yl + 1));
        t.modify(yr + 1, xr + 1, val * xr * yr);
    }
};

Ссылки

• Дерево Фенвика
• Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays