Prefix Sum array бэлдээд, дурын хэсгийн нийлбэрийг ганц хасах үйлдлээр олдог арга.

Pre-IntermediateХугацаа: Бэлдэх O(n), асуулт бүр O(1)Санах ой: O(n)
HackerRank дээр бодох

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

a = [2, 5, 1, 4] (index 1-ээс). p array: p[0] = 0, p[1] = 2, p[2] = 7, p[3] = 8, p[4] = 12.

a[2] + a[3] + a[4] хэд вэ? p[4] − p[1] = 12 − 2 = 10. Шалгая: 5 + 1 + 4 = 10. Ганц хасалт хийлээ.

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

Асуулт бүрт l-ээс r хүртэл нэмбэл нэг асуулт n хүртэл алхам. n ба асуултын тоо хоёулаа 10⁵ бол 10¹⁰ алхам, хэт удаан.

Оронд нь нэг удаа бэлдье: p[i] нь эхний i тооны нийлбэр. Тэгвэл a[l] + … + a[r] нь эхний r тооны нийлбэрээс эхний l - 1 тооны нийлбэрийг хассантай тэнцүү: p[r] - p[l - 1]. Асуулт бүрт ганц хасалт.

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

p[i]
a[1] + … + a[i]. p[0] = 0 нь хоосон нийлбэр.
l, r
Асуултын хэсгийн хоёр зах, хоёулаа хэсэгт орно. Index 1-ээс эхэлнэ.
p[r] - p[l - 1]
Асуултын хариу.
long long
Нийлбэр 10⁵ · 10⁹ хүртэл өсөж болох тул p-г long long гэж зарлана.
a
0
3
1
1
2
4
3
1
4
5
5
9
6
2
7
6
8
p
0
0
1
2
3
4
5
6
7
8

Эхлээд p-г бөглөнө: p[i] нь эхний i тооны нийлбэр, p[0] = 0. Дараа нь асуулт бүрт ганц хасалтаар хариулна.

Алхам 1 / 11
Хурд
  • Нэмж буй a[i]
  • Шинэ p[i]
  • Ашиглах p
  • Асуусан хэсэг
  • Бөглөсөн p
Слайд 1 / 6

Олон асуулт

«a[3] + … + a[6] хэд вэ?» гэх мэт асуулт олон ирвэл тоонуудыг дахин дахин нэмэх нь удаан. Нэг удаа бэлдээд хурдан хариулъя.

prefix-sum.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, a[100005];
long long p[100005];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + a[i];
}
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << p[r] - p[l - 1] << '\n';
}
return 0;
}

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

Array-н олон хэсгийн нийлбэрийг маш хурдан олох. Олон асуулттай олимпиадын бодлогод хамгийн их хэрэглэгддэг арга.

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

1. p[0] = 0. 2. i = 1 … n бүрт p[i] = p[i − 1] + a[i]. Энэ нь эхний i тооны нийлбэр. 3. a[l] + … + a[r] = p[r] − p[l − 1]. 4. Бэлдэхэд n алхам, асуулт бүрт ганц хасалт хийнэ. Оролт: n, n тоо, асуултын тоо q, дараа нь q мөрөнд «l r» (index 1-ээс эхэлнэ).

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

p[r] дотор a[1]-ээс a[r] хүртэлх бүх тоо, p[l - 1] дотор a[1]-ээс a[l − 1] хүртэлх бүх тоо орсон. Хасахад зөвхөн a[l]-ээс a[r] хүртэлх тоонууд үлдэнэ.

Бэлдэхэд O(n), асуулт бүрт O(1). n ба асуултын тоо 100 000 бол нийт 200 000 орчим үйлдэл. Энгийн аргаар 10¹⁰ байсан.

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

  • p-г int гэж зарлах. 10⁵ тоо, тус бүр 10⁹ бол нийлбэр 10¹⁴ хүрч int-ээс хэтэрнэ.
  • p[r] - p[l] гэж бичих. Тэгвэл a[l] өөрөө хасагдчихна. Зөв нь p[l - 1].
  • Index 0-ээс эхэлсэн array дээр l = 0 үед p[l - 1] нь p[-1] болно. Index 1-ээс эхэлбэл энэ асуудал гарахгүй.
  • Асуулт бүрт endl хэвлэх. 10⁵ мөрөнд endl удаан, '\n' хэрэглэ.

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

  • l = r: хариу нь a[l] өөрөө.
  • l = 1: p[0] = 0 хасагдана, хариу p[r].
  • Бүтэн array (l = 1, r = n): хариу p[n].
  • Сөрөг тоо байсан ч арга яг адил ажиллана.

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

  1. Анхдагч жишээ 3 1 4 1 5 9 2 6 дээр p[6] хэд вэ?

    Хариу харах

    23: 3 + 1 + 4 + 1 + 5 + 9.

  2. Тэгвэл l = 3, r = 6 асуултын хариу хэд вэ?

    Хариу харах

    19. p[6] − p[2] = 23 − 4.

  3. Яагаад p[0] хэрэгтэй вэ?

    Хариу харах

    l = 1 үед p[l - 1] = p[0] = 0 хасагдах ёстой. Тэгснээр тусад нь шалгах шаардлагагүй болно.

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

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

  1. 1.a = [4, -2, 7, 1, 3] (index 1-ээс) дээр p array-г бичээд l = 2, r = 4 асуултад хариул.

    Hint харах

    Сөрөг тоо байсан ч яг адилхан нэмнэ.

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

    p = [0, 4, 2, 9, 10, 13]. Хариу: p[4] − p[1] = 10 − 4 = 6.

  2. 2.Хэсгийн нийлбэрийн оронд хэсгийн дундаж утгыг (бүхэл хэсгээр) хэвлэ.

    Hint харах

    Хэсэгт хэдэн тоо байгаа вэ?

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

    (p[r] - p[l - 1]) / (r - l + 1). Хэсгийн урт нь r - l + 1.

  3. 3.n × m хүснэгт өгөгдсөн. Олон асуулт ирнэ: тэгш өнцөгт хэсгийн нийлбэрийг ол.

    Hint харах

    p[i][j] нь (1, 1)-ээс (i, j) хүртэлх тэгш өнцөгтийн нийлбэр.

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

    p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1]. Асуулт: p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1]. Бэлдэхэд O(nm), асуулт бүрт O(1).

Жишээ

Оролт

8
3 1 4 1 5 9 2 6
2
3 6
1 8

Гаралт

19
31

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

Бодлого

Хичээл

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