Варианты дерева Фенвика: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
 
(не показано 7 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Одномерное дерево Фенвика ==
== Одномерное дерево Фенвика ==


  int a[MAX_SIZE];
  struct BIT {
    vector<int> f;
   
   
int alpha(int x) {
    BIT(int size) : f(size) {}
    int res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        res += a[i];
    return res;
}
   
   
  void modifyAlphas(int x, int val) {
    int query(int r) {
    for (int i = x; i < MAX_SIZE; i |= i + 1)
        int res = 0;
        a[i] += val;
        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;
    }
  };


=== Запрос суммы на отрезке, изменение отдельных элементов ===
=== Запрос суммы на отрезке, изменение отдельных элементов ===
<tt>alpha(x)</tt> &mdash; сумма элементов от <tt>0</tt>-го до <tt>x</tt>-го.
t.query(r) сумма элементов от 0-го до r-го.


  int sum(int x) {
  struct BITRangeSumPointAdd {
     return alpha(x);
     BIT t;
}
   
   
  void add(int x, int val) {
    BITRangeSumPointAdd(int size) : t(size) {}
    modifyAlphas(x, val);
  }
    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);
    }
  };


=== Запрос значений отдельных элементов, изменение на отрезке ===
=== Запрос значений отдельных элементов, изменение на отрезке ===
<tt>alpha(x)</tt> &mdash; значение <tt>x</tt>-го элемента.
t.query(i) значение i-го элемента.


  int get(int x) {
  struct BITPointSumRangeAdd {
    return alpha(x);
    BIT t;
}
    BITPointSumRangeAdd(int size) : t(size) {}
    int get(int i) {
        return t.query(i);
    }
   
   
void add(int l, int r, int val) {
    void add(int l, int r, int val) {
    modifyAlphas(l, val);
        t.modify(l, val);
    modifyAlphas(r + 1, -val);
        t.modify(r + 1, -val);
  }
    }
  };


=== Запрос суммы на отрезке, изменение на отрезке ===
=== Запрос суммы на отрезке, изменение на отрезке ===
<tt>beta(x) * x + alpha(x)</tt> &mdash; сумма элементов от <tt>0</tt>-го до <tt>x</tt>-го.
tx.query(r) * r + t.query(r) сумма элементов от 0-го до r-го.
 
[[Файл:fenwick_range_1d.png|thumb|right|360px]]
  int sum(int x) {
struct BITRangeSumRangeAdd {
    return beta(x) * x + alpha(x);
    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) {
    void add(int l, int r, int val) {
    modifyBetas(l, val);
        tx.modify(l, val);
    modifyAlphas(l, val * (-l + 1));
        tx.modify(r + 1, -val);
    modifyBetas(r + 1, -val);
        t.modify(l, val * (-l + 1));
    modifyAlphas(r + 1, val * r);
        t.modify(r + 1, val * r);
  }  
    }
  };


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


  int a[MAX_SIZE][MAX_SIZE];
  struct BIT2D {
    vector<vector<int>> f;
    BIT2D(int h, int w) : f(h, vector<int>(w)) {}
   
   
int alpha(int x, int y) {
    int query(int yr, int xr) {
    int res = 0;
        int res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        for (int y = yr; y >= 0; y = (y & (y + 1)) - 1)
        for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
            for (int x = xr; x >= 0; x = (x & (x + 1)) - 1)
            res += a[i][j];
                res += f[y][x];
    return res;
        return res;
}
    }
   
   
void modifyAlphas(int x, int y, int val) {
    void modify(int cellY, int cellX, int val) {
    for (int i = x; i < MAX_SIZE; i |= i + 1)
        for (int y = cellY; y < f.size(); y |= y + 1)
        for (int j = y; j < MAX_SIZE; j |= j + 1)
            for (int x = cellX; x < f[0].size(); x |= x + 1)
            a[i][j] += val;
                f[y][x] += val;
  }
    }
  };


=== Запрос суммы на прямоугольнике, изменение отдельных элементов ===
=== Запрос суммы на прямоугольнике, изменение отдельных элементов ===
<tt>alpha(x, y)</tt> &mdash; сумма элементов от <tt>(0; 0)</tt>-го до <tt>(x; y)</tt>-го.
t.query(yr, xr) сумма элементов от (0; 0)-го до (yr; xr)-го.


  int sum(int x, int y) {
  struct BIT2DRangeSumPointAdd {
     return alpha(x, y);
     BIT2D t;
}
   
   
  void add(int x, int y, int val) {
    BIT2DRangeSumPointAdd(int h, int w) : t(h, w) {}
    modifyAlphas(x, y, val);
  }
    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);
    }
  };


=== Запрос значений отдельных элементов, изменение на прямоугольнике ===
=== Запрос значений отдельных элементов, изменение на прямоугольнике ===
<tt>alpha(x, y)</tt> &mdash; значение <tt>(x; y)</tt>-го элемента.
t.query(y, x) значение (y; x)-го элемента.


  int get(int x, int y) {
  struct BIT2DPointSumRangeAdd {
    return alpha(x, y);
    BIT2D t;
}
    BIT2DPointSumRangeAdd(int h, int w) : t(h, w) {}
    int get(int y, int x) {
        return t.query(y, x);
    }
   
   
void add(int lx, int rx, int ly, int ry, int val) {
    void add(int yl, int xl, int yr, int xr, int val) {
    modifyAlphas(lx, ly, val);
        t.modify(yl, xl, val);
    modifyAlphas(lx, ry + 1, -val);
        t.modify(yr + 1, xl, -val);
    modifyAlphas(rx + 1, ly, -val);
        t.modify(yl, xr + 1, -val);
    modifyAlphas(rx + 1, ry + 1, val);
        t.modify(yr + 1, xr + 1, val);
  }
    }
  };


=== Запрос суммы на прямоугольнике, изменение на прямоугольнике ===
=== Запрос суммы на прямоугольнике, изменение на прямоугольнике ===
<tt>delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y)</tt> &mdash; сумма элементов от <tt>(0; 0)</tt>-го до <tt>(x; y)</tt>-го.
tyx.query(yr, xr) * yr * xr + ty.query(yr, xr) * yr + tx.query(yr, xr) * xr + t.query(yr, xr) сумма элементов от (0; 0)-го до (yr; xr)-го.
 
[[Файл:fenwick_range_2d.png|thumb|right|360px]]
  int sum(int x, int y) {
struct BIT2DRangeSumRangeAdd {
    return delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y);
    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 lx, int rx, int ly, int ry, int val) {
    void add(int yl, int xl, int yr, int xr, int val) {
    modifyDeltas(lx, ly, val);
        tyx.modify(yl, xl, val);
    modifyGammas(lx, ly, val * (-lx + 1));
        tyx.modify(yr + 1, xl, -val);
    modifyBetas(lx, ly, val * (-ly + 1));
        tyx.modify(yl, xr + 1, -val);
    modifyAlphas(lx, ly, val * (-lx + 1) * (-ly + 1));
        tyx.modify(yr + 1, xr + 1, val);
   
   
    modifyDeltas(lx, ry + 1, -val);
        ty.modify(yl, xl, val * (-xl + 1));
    modifyGammas(lx, ry + 1, -val * (-lx + 1));
        ty.modify(yr + 1, xl, -val * (-xl + 1));
    modifyBetas(lx, ry + 1, val * ry);
        ty.modify(yl, xr + 1, val * xr);
    modifyAlphas(lx, ry + 1, val * (-lx + 1) * ry);
        ty.modify(yr + 1, xr + 1, -val * xr);
   
   
    modifyDeltas(rx + 1, ly, -val);
        tx.modify(yl, xl, val * (-yl + 1));
    modifyGammas(rx + 1, ly, val * rx);
        tx.modify(yr + 1, xl, val * yr);
    modifyBetas(rx + 1, ly, -val * (-ly + 1));
        tx.modify(yl, xr + 1, -val * (-yl + 1));
    modifyAlphas(rx + 1, ly, val * rx * (-ly + 1));
        tx.modify(yr + 1, xr + 1, -val * yr);
   
   
    modifyDeltas(rx + 1, ry + 1, val);
        t.modify(yl, xl, val * (-xl + 1) * (-yl + 1));
    modifyGammas(rx + 1, ry + 1, -val * rx);
        t.modify(yr + 1, xl, val * (-xl + 1) * yr);
    modifyBetas(rx + 1, ry + 1, -val * ry);
        t.modify(yl, xr + 1, val * xr * (-yl + 1));
    modifyAlphas(rx + 1, ry + 1, val * rx * ry);
        t.modify(yr + 1, xr + 1, val * xr * yr);
  }
    }
  };


== Ссылки ==
== Ссылки ==
* [[Дерево Фенвика]]
* [[Дерево Фенвика]]
* [[Дерево Фенвика с модификацией на отрезке]]
* [http://arxiv.org/pdf/1311.6093v4.pdf Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays]
* [http://arxiv.org/pdf/1311.6093v4.pdf Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays]


[[Category:Структуры данных для задач RSQ/RMQ]]
[[Category:Структуры данных для задач RSQ/RMQ]]

Текущая версия от 02:34, 2 февраля 2023

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

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-го.

Fenwick range 1d.png
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)-го.

Fenwick range 2d.png
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);
    }
};

Ссылки