Агуулгыг алгасах

Фенвикийн мод

$f$ нь ямар нэг бүлгийн үйлдэл (нэгж элемент ба урвуу элементтэй олонлог дээрх associative хоёрлосон функц), $A$ нь $N$ урттай бүхэл тоонуудын массив байг. $f$-ийн инфикс тэмдэглэгээг $*$ гэж тэмдэглэе; өөрөөр хэлбэл дурын бүхэл тоо $x,y$-ийн хувьд $f(x,y) = x*y$. (Энэ нь associative тул инфикс тэмдэглэгээ ашиглахдаа бид $f$-г хэрэглэх дарааллын хаалтыг орхино.)

Фенвикийн мод гэдэг нь дараах өгөгдлийн бүтэц юм:

  • өгөгдсөн $[l, r]$ интервал дахь $f$ функцийн утгыг (өөрөөр хэлбэл $A_l * A_{l+1} * \dots * A_r$) $O(\log N)$ хугацаанд тооцоолно
  • $A$-ийн элементийн утгыг $O(\log N)$ хугацаанд шинэчилнэ
  • $O(N)$ санах ой шаардана ($A$-д шаардагдахтай ижил хэмжээ)
  • ашиглах, кодлоход, ялангуяа олон хэмжээст массивын хувьд амархан

Фенвикийн модны хамгийн түгээмэл хэрэглээ бол интервалын нийлбэрийг тооцоолох явдал юм. Жишээ нь бүхэл тооны олонлог дээрх нэмэхийг бүлгийн үйлдэл болгон ашиглавал буюу $f(x,y) = x + y$: энэ тохиолдолд хоёрлосон үйлдэл $*$ нь $+$ болох тул $A_l * A_{l+1} * \dots * A_r = A_l + A_{l+1} + \dots + A_{r}$.

Фенвикийн модыг мөн Хоёртоор индексжүүлсэн мод (Binary Indexed Tree, BIT) гэж нэрлэдэг. Үүнийг анх "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994) гэсэн өгүүлэлд тайлбарласан.

Тайлбар

Тойм

Энгийн байлгах үүднээс бид $f$ функцийг бүхэл тооны дээр $f(x,y) = x + y$ гэж тодорхойлсон гэж үзнэ.

Бидэнд $A[0 \dots N-1]$ бүхэл тоонуудын массив өгөгдсөн гэж бодъё. (Бид тэгээс эхлэх индекслэл ашиглаж байгааг анхаарна уу.) Фенвикийн мод гэдэг нь зүгээр л $T[0 \dots N-1]$ массив бөгөөд элемент бүр нь ямар нэг $[g(i), i]$ интервал дахь $A$-ийн элементүүдийн нийлбэртэй тэнцүү:

$$T_i = \sum_{j = g(i)}^{i}{A_j}$$

энд $g$ нь $0 \le g(i) \le i$-г хангадаг ямар нэг функц юм. Бид $g$-г дараагийн хэдэн догол мөрөнд тодорхойлно.

Энэ өгөгдлийн бүтцийг мод гэж нэрлэдэг, учир нь түүнийг мод хэлбэрээр сайхан дүрсэлж болдог боловч бид зангилаа, ирмэг бүхий жинхэнэ модыг загварчлах шаардлагагүй. Бид бүх асуулгыг зохицуулахын тулд зөвхөн $T$ массивыг хадгалахад л хангалттай.

Тэмдэглэл: Энд танилцуулсан Фенвикийн мод тэгээс эхлэх индекслэл ашигладаг. Олон хүн нэгээс эхлэх индекслэл ашигладаг Фенвикийн модны хувилбарыг ашигладаг. Иймд та хэрэгжүүлэлтийн хэсэгт нэгээс эхлэх индекслэл ашигладаг өөр хэрэгжүүлэлтийг мөн олох болно. Хоёр хувилбар нь хугацаа ба санах ойн complexity-ийн хувьд эквивалент.

Одоо бид дээр дурдсан хоёр үйлдлийн псевдокодыг бичиж болно. Доор бид $[0, r]$ интервал дахь $A$-ийн элементүүдийн нийлбэрийг олж, ямар нэг элемент $A_i$-г шинэчилнэ (нэмэгдүүлнэ):

def sum(int r):
    res = 0
    while (r >= 0):
        res += t[r]
        r = g(r) - 1
    return res

def increase(int i, int delta):
    for all j with g(j) <= i <= j:
        t[j] += delta

sum функц дараах байдлаар ажилладаг:

  1. Эхлээд энэ нь $[g(r), r]$ интервалын нийлбэрийг (өөрөөр хэлбэл $T[r]$) result-д нэмнэ.
  2. Дараа нь энэ нь $[g(g(r)-1), g(r)-1]$ интервал руу "үсэрч", энэ интервалын нийлбэрийг result-д нэмнэ.
  3. Энэ нь $[0, g(g( \dots g(r)-1 \dots -1)-1)]$-ээс $[g(-1), -1]$ руу "үсрэх" хүртэл үргэлжилнэ; энд sum функц үсрэхээ болино.

increase функц ижил зүйрлэлээр ажилладаг боловч энэ нь өсөх индексийн чиглэлд "үсэрдэг":

  1. $g(j) \le i \le j$ нөхцөлийг хангах $[g(j), j]$ хэлбэрийн интервал бүрийн нийлбэр delta-ээр нэмэгдэнэ; өөрөөр хэлбэл t[j] += delta. Тиймээс энэ нь $A_i$ орших интервалуудад харгалзах $T$ дэх бүх элементийг шинэчилнэ.

sum ба increase хоёулын complexity нь $g$ функцээс хамаарна. Бүх $i$-ийн хувьд $0 \le g(i) \le i$ байх $g$ функцийг сонгох олон арга бий. Жишээ нь $g(i) = i$ функц ажиллах ба энэ нь $T = A$-г өгнө (энэ тохиолдолд нийлбэрийн асуулга удаан). Бид мөн $g(i) = 0$ функцийг авч болно. Энэ нь угтвар нийлбэрийн массивд харгалзана (энэ тохиолдолд $[0, i]$ интервалын нийлбэрийг олоход зөвхөн тогтмол хугацаа авна; гэвч шинэчлэлт удаан). Фенвикийн модны алгоритмын ухаалаг хэсэг нь хоёр үйлдлийг хоёуланг $O(\log N)$ хугацаанд зохицуулж чадах $g$ функцийн тусгай тодорхойлолтыг хэрхэн ашигладагт оршино.

$g(i)$-ийн тодорхойлолт

$g(i)$-ийн тооцоог дараах энгийн үйлдэл ашиглан тодорхойлно: бид $i$-ийн хоёртын дүрслэл дэх сүүлийн бүх $1$ битийг $0$ битээр солино.

Өөрөөр хэлбэл хэрэв хоёртоор $i$-ийн хамгийн бага утгатай орон $0$ бол $g(i) = i$. Эс бөгөөс хамгийн бага утгатай орон $1$ бөгөөд бид энэ $1$ ба бусад бүх сүүлийн $1$-ийг авч урвуулна.

Жишээ нь бид

$$\begin{align} g(11) = g(1011_2) = 1000_2 &= 8 \\\\ g(12) = g(1100_2) = 1100_2 &= 12 \\\\ g(13) = g(1101_2) = 1100_2 &= 12 \\\\ g(14) = g(1110_2) = 1110_2 &= 14 \\\\ g(15) = g(1111_2) = 0000_2 &= 0 \\\\ \end{align}$$

Дээр тайлбарласан тривиаль биш үйлдлийн хувьд битийн үйлдэл ашигласан энгийн хэрэгжүүлэлт бий:

$$g(i) = i ~\&~ (i+1),$$

энд $\&$ нь битийн AND оператор. Энэ шийдэл дээр тайлбарласан үйлдэлтэй ижил зүйл хийдэг гэдэгт итгэхэд хэцүү биш.

Одоо бид зөвхөн $g(j) \le i \le j$ байх бүх $j$-ээр давтах аргыг олох хэрэгтэй.

$i$-ээс эхлээд сүүлийн тавигдаагүй битийг урвуулах замаар бид ийм бүх $j$-г олж болохыг харахад амархан. Энэ үйлдлийг бид $h(j)$ гэж нэрлэнэ. Жишээ нь $i = 10$-ийн хувьд бид:

$$\begin{align} 10 &= 0001010_2 \\\\ h(10) = 11 &= 0001011_2 \\\\ h(11) = 15 &= 0001111_2 \\\\ h(15) = 31 &= 0011111_2 \\\\ h(31) = 63 &= 0111111_2 \\\\ \vdots & \end{align}$$

Гайхах зүйлгүй нь битийн үйлдэл ашиглан $h$-г гүйцэтгэх энгийн арга мөн бий:

$$h(j) = j ~|~ (j+1),$$

энд $|$ нь битийн OR оператор.

Дараах зураг Фенвикийн модыг мод хэлбэрээр тайлбарлаж болох нэг хувилбарыг харуулна. Модны зангилаанууд өөрсдийн бүрхэх интервалуудыг харуулна.

Binary Indexed Tree

Implementation

Finding sum in one-dimensional array

Here we present an implementation of the Fenwick tree for sum queries and single updates.

The normal Fenwick tree can only answer sum queries of the type $[0, r]$ using sum(int r), however we can also answer other queries of the type $[l, r]$ by computing two sums $[0, r]$ and $[0, l-1]$ and subtract them. This is handled in the sum(int l, int r) method.

Also this implementation supports two constructors. You can create a Fenwick tree initialized with zeros, or you can convert an existing array into the Fenwick form.

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

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

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

Linear construction

The above implementation requires $O(N \log N)$ time. It's possible to improve that to $O(N)$ time.

The idea is, that the number $a[i]$ at index $i$ will contribute to the range stored in $bit[i]$, and to all ranges that the index $i | (i + 1)$ contributes to. So by adding the numbers in order, you only have to push the current sum further to the next range, where it will then get pushed further to the next range, and so on.

FenwickTree(vector<int> const &a) : FenwickTree(a.size()){
    for (int i = 0; i < n; i++) {
        bit[i] += a[i];
        int r = i | (i + 1);
        if (r < n) bit[r] += bit[i];
    }
}

Finding minimum of $[0, r]$ in one-dimensional array

It is obvious that there is no easy way of finding minimum of range $[l, r]$ using Fenwick tree, as Fenwick tree can only answer queries of type $[0, r]$. Additionally, each time a value is update'd, the new value has to be smaller than the current value. Both significant limitations are because the $min$ operation together with the set of integers doesn't form a group, as there are no inverse elements.

struct FenwickTreeMin {
    vector<int> bit;
    int n;
    const int INF = (int)1e9;

    FenwickTreeMin(int n) {
        this->n = n;
        bit.assign(n, INF);
    }

    FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            update(i, a[i]);
    }

    int getmin(int r) {
        int ret = INF;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret = min(ret, bit[r]);
        return ret;
    }

    void update(int idx, int val) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] = min(bit[idx], val);
    }
};

Note: it is possible to implement a Fenwick tree that can handle arbitrary minimum range queries and arbitrary updates. The paper Efficient Range Minimum Queries using Binary Indexed Trees describes such an approach. However with that approach you need to maintain a second binary indexed tree over the data, with a slightly different structure, since one tree is not enough to store the values of all elements in the array. The implementation is also a lot harder compared to the normal implementation for sums.

Finding sum in two-dimensional array

As claimed before, it is very easy to implement Fenwick Tree for multidimensional array.

struct FenwickTree2D {
    vector<vector<int>> bit;
    int n, m;

    // init(...) { ... }

    int sum(int x, int y) {
        int ret = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
                ret += bit[i][j];
        return ret;
    }

    void add(int x, int y, int delta) {
        for (int i = x; i < n; i = i | (i + 1))
            for (int j = y; j < m; j = j | (j + 1))
                bit[i][j] += delta;
    }
};

One-based indexing approach

For this approach we change the requirements and definition for $T[]$ and $g()$ a little bit. We want $T[i]$ to store the sum of $[g(i)+1; i]$. This changes the implementation a little bit, and allows for a similar nice definition for $g(i)$:

def sum(int r):
    res = 0
    while (r > 0):
        res += t[r]
        r = g(r)
    return res

def increase(int i, int delta):
    for all j with g(j) < i <= j:
        t[j] += delta

The computation of $g(i)$ is defined as: toggling of the last set $1$ bit in the binary representation of $i$.

$$\begin{align} g(7) = g(111_2) = 110_2 &= 6 \\\\ g(6) = g(110_2) = 100_2 &= 4 \\\\ g(4) = g(100_2) = 000_2 &= 0 \\\\ \end{align}$$

The last set bit can be extracted using $i ~\&~ (-i)$, so the operation can be expressed as:

$$g(i) = i - (i ~\&~ (-i)).$$

And it's not hard to see, that you need to change all values $T[j]$ in the sequence $i,~ h(i),~ h(h(i)),~ \dots$ when you want to update $A[j]$, where $h(i)$ is defined as:

$$h(i) = i + (i ~\&~ (-i)).$$

As you can see, the main benefit of this approach is that the binary operations complement each other very nicely.

The following implementation can be used like the other implementations, however it uses one-based indexing internally.

struct FenwickTreeOneBasedIndexing {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTreeOneBasedIndexing(int n) {
        this->n = n + 1;
        bit.assign(n + 1, 0);
    }

    FenwickTreeOneBasedIndexing(vector<int> a)
        : FenwickTreeOneBasedIndexing(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int idx) {
        int ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }

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

    void add(int idx, int delta) {
        for (++idx; idx < n; idx += idx & -idx)
            bit[idx] += delta;
    }
};

Интервалын үйлдлүүд

Фенвикийн мод дараах интервалын үйлдлүүдийг дэмжиж чадна:

  1. Цэгийн шинэчлэл ба интервалын асуулга
  2. Интервалын шинэчлэл ба цэгийн асуулга
  3. Интервалын шинэчлэл ба интервалын асуулга

1. Цэгийн шинэчлэл ба интервалын асуулга

Энэ бол дээр тайлбарласан ердийн Фенвикийн мод юм.

2. Интервалын шинэчлэл ба цэгийн асуулга

Энгийн заль мэх ашиглан бид эсрэг үйлдлүүдийг ч хийж болно: интервалыг нэмэгдүүлэх, ганц утгыг асуух.

Фенвикийн модыг тэгээр эхлүүлсэн байг. Бид $[l, r]$ интервалыг $x$-ээр нэмэгдүүлэхийг хүсэж байна гэж бодъё. Бид Фенвикийн мод дээр add(l, x) ба add(r+1, -x) гэсэн хоёр цэгийн шинэчлэл үйлдэл хийнэ.

Хэрэв бид $A[i]$-ийн утгыг авахыг хүсвэл бид зүгээр л ердийн интервалын нийлбэрийн аргаар угтвар нийлбэрийг авах хэрэгтэй. Энэ яагаад үнэн болохыг харахын тулд бид өмнөх нэмэгдүүлэх үйлдэлд дахин анхаарлаа хандуулж болно. Хэрэв $i < l$ бол хоёр шинэчлэлийн үйлдэл асуулгад нөлөөлөхгүй бөгөөд бид $0$ нийлбэрийг олно. Хэрэв $i \in [l, r]$ бол бид эхний шинэчлэлийн үйлдлээс болж $x$ хариуг олно. Хэрэв $i > r$ бол хоёр дахь шинэчлэлийн үйлдэл эхнийхийн нөлөөг цуцална.

Дараах хэрэгжүүлэлт нэгээс эхлэх индекслэл ашигладаг.

void add(int idx, int val) {
    for (++idx; idx < n; idx += idx & -idx)
        bit[idx] += val;
}

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

int point_query(int idx) {
    int ret = 0;
    for (++idx; idx > 0; idx -= idx & -idx)
        ret += bit[idx];
    return ret;
}

Тэмдэглэл: мэдээж range_add(i, i, val)-ээр ганц цэг $A[i]$-г нэмэгдүүлэх боломжтой.

3. Интервалын шинэчлэл ба интервалын асуулга

Интервалын шинэчлэл ба интервалын асуулга хоёуланг дэмжихийн тулд бид тэгээр эхлүүлсэн $B_1[]$ ба $B_2[]$ гэсэн хоёр BIT ашиглана.

Бид $[l, r]$ интервалыг $x$ утгаар нэмэгдүүлэхийг хүсэж байна гэж бодъё. Өмнөх аргатай адилаар бид $B_1$ дээр хоёр цэгийн шинэчлэл хийнэ: add(B1, l, x) ба add(B1, r+1, -x). Мөн бид $B_2$-г шинэчилнэ. Дэлгэрэнгүйг дараа тайлбарлана.

def range_add(l, r, x):
    add(B1, l, x)
    add(B1, r+1, -x)
    add(B2, l, x*(l-1))
    add(B2, r+1, -x*r))
$(l, r, x)$ интервалын шинэчлэлийн дараа интервалын нийлбэр асуулга дараах утгуудыг буцаах ёстой:

$$ sum[0, i]= \begin{cases} 0 & i < l \\\\ x \cdot (i-(l-1)) & l \le i \le r \\\\ x \cdot (r-l+1) & i > r \\\\ \end{cases} $$

Бид интервалын нийлбэрийг хоёр гишүүний зөрүү хэлбэрээр бичиж болно, энд эхний гишүүнд $B_1$-г, хоёр дахь гишүүнд $B_2$-г ашиглана. Асуулгуудын зөрүү нь бидэнд $[0, i]$ дээрх угтвар нийлбэрийг өгнө.

$$\begin{align} sum[0, i] &= sum(B_1, i) \cdot i - sum(B_2, i) \\\\ &= \begin{cases} 0 \cdot i - 0 & i < l\\\\ x \cdot i - x \cdot (l-1) & l \le i \le r \\\\ 0 \cdot i - (x \cdot (l-1) - x \cdot r) & i > r \\\\ \end{cases} \end{align} $$

Сүүлийн илэрхийлэл нь шаардлагатай гишүүдтэй яг тэнцүү. Тиймээс бид $B_1[i]\times i$-г үржүүлэхэд илүүдэл гишүүдийг арилгахад $B_2$-г ашиглаж болно.

Бид $l-1$ ба $r$-ийн угтвар нийлбэрүүдийг тооцоолж, тэдгээрийн зөрүүг дахин авах замаар дурын интервалын нийлбэрийг олж болно.

def add(b, idx, x):
    while idx <= N:
        b[idx] += x
        idx += idx & -idx

def range_add(l,r,x):
    add(B1, l, x)
    add(B1, r+1, -x)
    add(B2, l, x*(l-1))
    add(B2, r+1, -x*r)

def sum(b, idx):
    total = 0
    while idx > 0:
        total += b[idx]
        idx -= idx & -idx
    return total

def prefix_sum(idx):
    return sum(B1, idx)*idx -  sum(B2, idx)

def range_sum(l, r):
    return prefix_sum(r) - prefix_sum(l-1)

Дасгал бодлогууд

Бусад эх сурвалж