Ганц array-гээр эхний r тооны нийлбэрийг олж, тоо нэмэхийг хурдан хийдэг богинохон бүтэц.

Advanced & LegendХугацаа: O((n + q) log n)Санах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

a = [3, 1, 4, 1, 5] (index 1-ээс). Fenwick Tree-д bit = [3, 4, 4, 9, 5] болно: bit[2] = a[1] + a[2], bit[4] = a[1] + … + a[4] гэх мэт.

Эхний 5 тооны нийлбэр: bit[5] + bit[4] = 5 + 9 = 14. Эхний 3 тооны нийлбэр: bit[3] + bit[2] = 4 + 4 = 8.

Энгийн аргаас санаа руу

Энгийн арга бол асуулт бүрт эхний r тоог loop-оор нэмэх. Асуулт олон бол O(n·q) болж удаан. Prefix sum array хурдан хариулах ч нэг тоо өөрчлөгдөхөд O(n) prefix-ийг шинэчилнэ.

Fenwick Tree нь тоо бүрийг log n ширхэг сагсанд хуваарилна. bit[i] нь a[i]-гаар төгссөн, i & -i урттай хэсгийн нийлбэр. Аливаа prefix log n сагснаас бүрдэнэ. Нэг тоо log n сагсанд л ордог.

Нэр томьёо ба тэмдэглэгээ

bit[i]
a[i - (i & -i) + 1 .. i] хэсгийн нийлбэр. Index 1-ээс эхэлнэ.
i & -i
i-г хоёртын системээр бичихэд хамгийн баруун талд байгаа 1 бит. 12 = 1100 бол 4.
add(i, x)
a[i] дээр x-ийг нэмнэ: i += i & -i гэж дээш үсэрсээр бүх сагсыг шинэчилнэ.
sum(i)
a[1] + … + a[i]-г олно: i -= i & -i гэж доош үсэрсээр сагснуудыг нэмнэ.
a
5
1
8
2
6
3
3
4
2
5
7
6
2
7
6
8
bit
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8

bit[i] нь a array-н нэг хэсгийн нийлбэрийг хадгална. Хэсгийн урт нь i & -i. Эхлээд a array-н тоо бүрийг нэг нэгээр нь bit руу нэмье.

Алхам 1 / 28
Хурд
  • Одоогийн тоо, нүд
  • Шинэчилсэн нүд
  • Энэ нүдний хэсэг
  • Нийлбэрт орсон
  • Хариу
Слайд 1 / 6

Жижигхэн ч хүчтэй

Fenwick Tree ганц bit array-гээр эхний r тооны нийлбэрийг олж, тоо нэмэхийг хурдан хийдэг. Код нь маш богино тул тэмцээн дээр 2 минутад бичнэ.

fenwick-tree.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long bit[100005];
void add(int i, long long x) {
for (; i <= n; i += i & -i) {
bit[i] += x;
}
}
long long sum(int i) {
long long s = 0;
for (; i > 0; i -= i & -i) {
s += bit[i];
}
return s;
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
add(i, x);
}
while (q--) {
int type, i;
cin >> type >> i;
if (type == 1) {
long long x;
cin >> x;
add(i, x);
} else {
cout << sum(i) << '\n';
}
}
return 0;
}

Юунд хэрэгтэй вэ?

a[i] дээр тоо нэмэх, эхний r тооны нийлбэрийг олох query-д O(log n) хугацаанд хариулна. Segment Tree-гийн хийдэг ажлын ихэнхийг хэд дахин богино кодоор хийнэ.

Яаж ажилладаг вэ?

1. bit[i] нь a[i]-гаар төгссөн, i & -i урттай хэсгийн нийлбэрийг хадгална. i & -i нь i-г хоёртын системээр бичихэд хамгийн баруун талд байгаа 1 бит. 2. Нэмэх (add): bit[i] дээр x-ийг нэмээд i += i & -i гэж дээш үсэрнэ. a[i]-г агуулсан бүх нүд шинэчлэгдэнэ. 3. Нийлбэр (sum): s дээр bit[i]-г нэмээд i -= i & -i гэж доош үсэрнэ. i = 0 болмогц зогсоно. 4. Эхлээд тоо бүрийг add функцээр нэмж бэлдэнэ. a[l..r] хэсгийн нийлбэр = sum(r) − sum(l − 1). Оролт: эхний мөрөнд n ба q, дараагийн мөрөнд n тоо. Дараа нь q мөр: "1 i x" (a[i] дээр x нэмэх) эсвэл "2 i" (эхний i тооны нийлбэр). Index 1-ээс эхэлнэ.

Яагаад зөв, хэр хурдан бэ?

sum(i) нь i-н 1 битүүдийг баруунаас нь нэг нэгээр арилгадаг. Алхам бүрт авсан сагснууд давхцахгүй, зэргэлдээ байрласан хэсгүүд бөгөөд нийлээд яг [1, i] болно: 7 = 4 + 2 + 1 тул bit[7], bit[6], bit[4] нь a[7], a[5..6], a[1..4]. add(i) нь a[i]-г агуулсан сагс бүрээр яг нэг удаа дамжина.

Хоёр үйлдэл хоёулаа битийн тоогоор, өөрөөр хэлбэл ихдээ log₂ n + 1 алхам хийнэ. n = 100 000 бол 17 орчим алхам. Санах ой нь ердөө n + 1 элементтэй array.

Түгээмэл алдаа

  • Index 0-ээс эхлүүлэх. i = 0 үед i & -i = 0 тул add хэзээ ч дуусахгүй. Index-ийг 1-ээс эхлүүл.
  • a[i] = x болгох гэж add(i, x) дуудах. Fenwick нэмдэг тул add(i, x - a[i]) гээд a[i]-г тусад нь хадгал.
  • Хэсгийн нийлбэрт sum(r) - sum(l) гэж бичих. Зөв нь sum(r) - sum(l - 1).
  • bit-ийг int болгох. Нийлбэр том бол long long хэрэгтэй.

Хязгаарын тохиолдол

  • sum(0): loop огт ажиллахгүй, 0 буцаана. l = 1 үед sum(l - 1) зөв ажиллана.
  • n нь 2-ын зэрэг: bit[n] нь бүх array-н нийлбэр.
  • Сөрөг x нэмэх: add хэвээрээ ажиллана, тоо буурна.

Өөрийгөө шалга

  1. bit[12] нь аль хэсгийн нийлбэрийг хадгалах вэ?

    Хариу харах

    a[9..12]. 12 & -12 = 4 тул урт нь 4.

  2. sum(13) бодоход аль нүднүүдийг нэмэх вэ?

    Хариу харах

    bit[13], bit[12], bit[8]. 13 → 12 → 8 → 0.

  3. n = 8 бол add(5, x) аль нүднүүдийг шинэчлэх вэ?

    Хариу харах

    bit[5], bit[6], bit[8]. 5 → 6 → 8 → 16 > 8.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 8, бүх a[i] = 1. bit array-г бөглө.

    Hint харах

    bit[i] нь i & -i ширхэг 1-ийн нийлбэр.

    Хариу ба тайлбар

    bit = [1, 2, 1, 4, 1, 2, 1, 8]. sum(8) = bit[8] = 8.

  2. 2.a[l..r] хэсгийн нийлбэрийг буцаадаг rangeSum(l, r) function бич.

    Hint харах

    Хоёр prefix-ийн зөрүү.

    Хариу ба тайлбар

    return sum(r) - sum(l - 1); Хоёр дуудлага тул O(log n) хэвээр.

  3. 3.Fenwick Tree ашиглан array дахь inversion-ий тоог O(n log n)-д ол. Тоонууд 1-ээс n хүртэл.

    Hint харах

    Зүүнээс баруун тийш явна. Өмнө нь гарсан тоонуудаас a[i]-гаас их нь хэд вэ?

    Хариу ба тайлбар

    i нь 0-ээс эхэлсэн байрлал гэе. Өмнө нь i тоо гарсан, тэдгээрийн sum(a[i]) нь a[i]-гаас их биш. Тиймээс cnt += i - sum(a[i]), дараа нь add(a[i], 1). [3, 1, 2, 5, 4] дээр хариу 3.

Жишээ

Оролт

8 3
5 8 6 3 2 7 2 6
2 7
1 3 4
2 7

Гаралт

33
37

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.