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

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

struct BIT {
    vector<int> f;

    BIT(int size) : f(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 i, int val) {
        for (; i < f.size(); i |= i + 1)
            f[i] += val;
    }
};

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

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

struct BITRangeSumPointAdd {
    BIT t;

    BITRangeSumPointAdd(int size) : t(size) {}

    int sum(int r) {
        return t.query(r);
    }

    int sum(int l, int r) {
        return sum(r) - (l ? sum(l - 1) : 0);
    }

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

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

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

struct BITPointSumRangeAdd {
    BIT t;

    BITPointSumRangeAdd(int size) : t(size) {}

    int get(int i) {
        return t.query(i);
    }

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

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

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

struct BITRangeSumRangeAdd {
    BIT t, tx;

    BITRangeSumRangeAdd(int size) : t(size), tx(size) {}

    int sum(int r) {
        return tx.query(r) * r + t.query(r);
    }

    int sum(int l, int r) {
        return sum(r) - (l ? sum(l - 1) : 0);
    }

    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 cellY, int cellX, int val) {
        for (int y = cellY; y < f.size(); y |= y + 1)
            for (int x = cellX; 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