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

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


  int f[MAX_SIZE];
  struct BIT {
    vector<int> f;
   
   
int query(int r) {
    BIT(int size) : f(size) {}
    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) {
    int query(int r) {
    for (int i = r; i < MAX_SIZE; i |= i + 1)
        int res = 0;
        f[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;
    }
  };


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


  int prefixSum(int r) {
  struct BITRangeSumPointAdd {
    return query(r);
    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 pos, int val) {
    void add(int i, int val) {
    modify(pos, val);
        t.modify(i, val);
  }
    }
  };


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


  int get(int pos) {
  struct BITPointSumRangeAdd {
     return query(pos);
     BIT t;
}
   
   
  void add(int l, int r, int val) {
    BITPointSumRangeAdd(int size) : t(size) {}
    modify(l, val);
   
    modify(r + 1, -val);
    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) &mdash; сумма элементов от 0-го до r-го.
tx.query(r) * r + t.query(r) сумма элементов от 0-го до r-го.
[[Файл:fenwick_range_1d.png|thumb|right|360px]]
[[Файл:fenwick_range_1d.png|thumb|right|360px]]
  int prefixSum(int r) {
  struct BITRangeSumRangeAdd {
     return Tx.query(r) * r + T.query(r);
     BIT t, tx;
}
   
   
  void add(int l, int r, int val) {
    BITRangeSumRangeAdd(int size) : t(size), tx(size) {}
    Tx.modify(l, val);
    Tx.modify(r + 1, -val);
    int sum(int r) {
    T.modify(l, val * (-l + 1));
        return tx.query(r) * r + t.query(r);
    T.modify(r + 1, val * 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);
    }
  };


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


  int f[MAX_SIZE][MAX_SIZE];
  struct BIT2D {
    vector<vector<int>> f;
   
   
int query(int ry, int rx) {
    BIT2D(int h, int w) : f(h, vector<int>(w)) {}
    int res = 0;
    for (int i = ry; i >= 0; i = (i & (i + 1)) - 1)
        for (int j = rx; j >= 0; j = (j & (j + 1)) - 1)
            res += f[i][j];
    return res;
}
   
   
  void modify(int ry, int rx, int val) {
    int query(int yr, int xr) {
    for (int i = ry; i < MAX_SIZE; i |= i + 1)
        int res = 0;
        for (int j = rx; j < MAX_SIZE; j |= j + 1)
        for (int y = yr; y >= 0; y = (y & (y + 1)) - 1)
            f[i][j] += val;
            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;
    }
  };


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


  int prefixSum(int ry, int rx) {
  struct BIT2DRangeSumPointAdd {
     return query(ry, rx);
     BIT2D t;
}
   
   
  void add(int ry, int rx, int val) {
    BIT2DRangeSumPointAdd(int h, int w) : t(h, w) {}
    modify(ry, rx, 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);
    }
  };


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


  int get(int ry, int rx) {
  struct BIT2DPointSumRangeAdd {
     return query(ry, rx);
     BIT2D t;
}
   
   
  void add(int ly, int lx, int ry, int rx, int val) {
    BIT2DPointSumRangeAdd(int h, int w) : t(h, w) {}
    modify(ly, lx, val);
   
    modify(ry + 1, lx, -val);
    int get(int y, int x) {
    modify(ly, rx + 1, -val);
        return t.query(y, x);
    modify(ry + 1, rx + 1, val);
    }
  }
    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(ry, rx) * ry * rx + Ty.query(ry, rx) * ry + Tx.query(ry, rx) * rx + T.query(ry, rx) &mdash; сумма элементов от (0; 0)-го до (ry; rx)-го.
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]]
[[Файл:fenwick_range_2d.png|thumb|right|360px]]
  int prefixSum(int ry, int rx) {
  struct BIT2DRangeSumRangeAdd {
    return Tyx.query(ry, rx) * ry * rx + Ty.query(ry, rx) * ry + Tx.query(ry, rx) * rx + T.query(ry, rx);
    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);
   
   
void add(int ly, int lx, int ry, int rx, int val) {
        t.modify(yl, xl, val * (-xl + 1) * (-yl + 1));
    Tyx.modify(ly, lx, val);
        t.modify(yr + 1, xl, val * (-xl + 1) * yr);
    Tyx.modify(ry + 1, lx, -val);
        t.modify(yl, xr + 1, val * xr * (-yl + 1));
    Tyx.modify(ly, rx + 1, -val);
        t.modify(yr + 1, xr + 1, val * xr * yr);
    Tyx.modify(ry + 1, rx + 1, val);
     }
   
  };
    Ty.modify(ly, lx, val * (-lx + 1));
    Ty.modify(ry + 1, lx, -val * (-lx + 1));
    Ty.modify(ly, rx + 1, val * rx);
    Ty.modify(ry + 1, rx + 1, -val * rx);
   
    Tx.modify(ly, lx, val * (-ly + 1));
    Tx.modify(ry + 1, lx, val * ry);
    Tx.modify(ly, rx + 1, -val * (-ly + 1));
    Tx.modify(ry + 1, rx + 1, -val * ry);
   
    T.modify(ly, lx, val * (-lx + 1) * (-ly + 1));
    T.modify(ry + 1, lx, val * (-lx + 1) * ry);
    T.modify(ly, rx + 1, val * rx * (-ly + 1));
     T.modify(ry + 1, rx + 1, val * rx * ry);
  }


== Ссылки ==
== Ссылки ==

Текущая версия от 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);
    }
};

Ссылки