Seqmentdə cəm (Həll təhlili)

Məsələ iki növ sorğunun emal edilməsini tələb edir: massivin bir elementinə qiymət mənimsətmək və $[l; r]$ [l; r] seqmentindəki elementlərin cəmini hesablamaq. Əgər yalnız massivin özünü saxlasaq, mənimsətmə $O (1)$ vaxtda yerinə yetirilir, lakin hər cəm sorğusu $O (n)$ əməliyyat tələb edir. Əgər prefiks cəmlərini saxlasaq, cəm $O (1)$ vaxtda hesablanır, lakin hər mənimsətmə $O (n)$ prefiks cəminin yenidən hesablanmasını tələb edir. Sorğuların sayı böyük olduqda hər iki yanaşma da çox yavaş olur.

Cəmlər üçün seqment ağacından istifadə edirik. Onun hər bir təpəsi öz seqmentinin elementlərinin cəmini saxlayır, daxili təpədəki qiymət isə onun iki övladının qiymətlərinin cəminə bərabərdir. Seqment ağacı hər iki əməliyyatı $O (lo g n)$ O(\log n) vaxtında yerinə yetirir. Cəm hesablanarkən seqmentin boş hissəsi $0$ -a — toplama üçün neytral elementə — uyğun gəlir.

Başlanğıcda massivin bütün elementləri sıfırdır, buna görə də ağacın bütün təpələrindəki cəmlər də sıfırdır. Ağac massivini sıfırlarla doldurmaq kifayətdir; ağacın ayrıca qurulmasına ehtiyac yoxdur.

Elementlərin qiymətləri $1 0^{9}$ 10^9-a çata bilər, buna görə seqmentdəki cəm $1 0^{5} \cdot 1 0^{9} = 1 0^{14}$ 10^5 \cdot 10^9 = 10^{14}-ə çata bilər və int tipinə sığmır. Ağacdakı qiymətlər long long tipində saxlanılır.

Fenvik ağacı istifadə edən həlli nəzərdən keçirək. O, hər biri $O (lo g n)$ O(\log n) vaxtında yerinə yetirilən iki əməliyyatı dəstəkləyir:

$a_{i}$ a_i elementinə $d e l t a$ ədədinin əlavə edilməsi;
prefiks cəminin hesablanması $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i.

Başlanğıcda massivin bütün elementləri sıfırdır, buna görə sıfırlarla doldurulmuş Fenvik ağacı artıq başlanğıc massivə uyğun gəlir. Sorğulardakı indekslər $1$ -dən $n$ -ə qədərdir; $a_{0}$ a_0 elementi istifadə olunmur və həmişə sıfırdır.

Mənimsətmə. Fenvik ağacı yalnız elementə ədəd əlavə edə bilər, lakin ona yeni qiymət mənimsədə bilməz. Lakin elementin cari qiymətini prefiks cəmləri vasitəsilə hesablamaq olar:

a_{i} = s u m (i) - s u m (i - 1)

a_i = sum(i) - sum(i - 1)

Buna görə $a_{i} = x$ a_i = x mənimsətməsi $a_{i}$ a_i-yə yeni və köhnə qiymətlər arasındakı fərqin əlavə edilməsi ilə əvəz olunur:

d e l t a = x - (s u m (i) - s u m (i - 1)) = x - s u m (i) + s u m (i - 1)

delta = x - (sum(i) - sum(i - 1)) = x - sum(i) + sum(i - 1)

Seqment üzrə cəm. $[l; r]$ [l; r] seqmentindəki elementlərin cəmi iki prefiks cəminin fərqinə bərabərdir:

a_{l} + a_{l + 1} + \dots + a_{r} = s u m (r) - s u m (l - 1)

a_l + a_{l+1} + \ldots + a_r = sum(r) - sum(l - 1)

Elementlərin qiymətləri $1 0^{9}$ 10^9-a çata bilər, buna görə cəmlər $1 0^{14}$ 10^{14}-ə çata bilər və long long tipində saxlanılır.

Misal

Başlanğıcda massiv sıfırlardan ibarətdir. $A 22$ , $A 31$ və $A 42$ sorğularından sonra massiv $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0) şəklini alır. Onun üçün seqment ağacı aşağıda göstərilmişdir. Hər təpədə onun seqmenti və bu seqmentdəki elementlərin cəmi göstərilir.

$A 31$ sorğusu yerinə yetirildikdə yalnız $[3]$ yarpağından kökə qədər olan yoldakı təpələr yenidən hesablanır: $[3]$ yarpağı $1$ qiymətini alır, $[1; 3]$ təpəsi — $2 + 1 = 3$ 2 + 1 = 3 qiymətini, $[1; 5]$ kökü isə — $3 + 2 = 5$ 3 + 2 = 5 qiymətini alır.

$Q 11$ , $Q 22$ , $Q 33$ , $Q 44$ və $Q 55$ sorğuları yarpaqların qiymətlərini qaytarır: $0, 2, 1, 2, 0$ 0, 2, 1, 2, 0. $Q 15$ sorğusunun seqmenti kökün seqmenti ilə üst-üstə düşür, buna görə cavab birbaşa kökdən götürülür və $5$ -ə bərabərdir (vurğulanmış təpə).

Misaldakı sorğuları Fenvik ağacı ilə simulyasiya edək, $n = 5$ n = 5. Başlanğıcda massiv $(0, 0, 0, 0, 0)$ (0, 0, 0, 0, 0)-dır. Hər mənimsətmə sorğusu üçün cədvəldə elementin köhnə qiymətinin necə hesablandığı və hansı ədədin əlavə edildiyi göstərilir; hər cəm sorğusu üçün isə prefiks cəmlərinin fərqi göstərilir.

sorğu	hesablama	nəticə
$A 22$	köhnə qiymət $s u m (2) - s u m (1) = 0 - 0 = 0$ sum(2) - sum(1) = 0 - 0 = 0, əlavə edilir $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 0, 0, 0)$ (0, 2, 0, 0, 0)
$A 31$	köhnə qiymət $s u m (3) - s u m (2) = 2 - 2 = 0$ sum(3) - sum(2) = 2 - 2 = 0, əlavə edilir $1 - 0 = 1$ 1 - 0 = 1	$(0, 2, 1, 0, 0)$ (0, 2, 1, 0, 0)
$A 42$	köhnə qiymət $s u m (4) - s u m (3) = 3 - 3 = 0$ sum(4) - sum(3) = 3 - 3 = 0, əlavə edilir $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0)
$Q 11$	$s u m (1) - s u m (0) = 0 - 0$ sum(1) - sum(0) = 0 - 0	$0$
$Q 22$	$s u m (2) - s u m (1) = 2 - 0$ sum(2) - sum(1) = 2 - 0	$2$
$Q 33$	$s u m (3) - s u m (2) = 3 - 2$ sum(3) - sum(2) = 3 - 2	$1$
$Q 44$	$s u m (4) - s u m (3) = 5 - 3$ sum(4) - sum(3) = 5 - 3	$2$
$Q 55$	$s u m (5) - s u m (4) = 5 - 5$ sum(5) - sum(4) = 5 - 5	$0$
$Q 15$	$s u m (5) - s u m (0) = 5 - 0$ sum(5) - sum(0) = 5 - 0	$5$

Məsələn, $Q 44$ sorğusundan əvvəl massiv $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0)-dır, buna görə $s u m (4) = 0 + 2 + 1 + 2 = 5$ sum(4) = 0 + 2 + 1 + 2 = 5, $s u m (3) = 0 + 2 + 1 = 3$ sum(3) = 0 + 2 + 1 = 3, cavab isə $5 - 3 = 2$ 5 - 3 = 2-dir.

Misalda bütün mənimsətmələr sıfır elementlərə tətbiq olunur. Gəlin təkrar mənimsətmə zamanı nə baş verəcəyinə baxaq, məsələn sonda $A 35$ sorğusuna. Köhnə qiymət $s u m (3) - s u m (2) = 3 - 2 = 1$ sum(3) - sum(2) = 3 - 2 = 1-dir, buna görə $a_{3}$ a_3-ə $5 - 1 = 4$ 5 - 1 = 4 əlavə olunur və element $5$ olur.

Alqoritmin tətbiqi

Seqment ağacı uzunluğu $4 \cdot M A X$ 4 \cdot MAX olan $S e g T r ee$ SegTree massivində saxlanılır, burada $M A X$ — massiv elementlərinin maksimum sayıdır. Seqmentdəki cəm int tipinin sərhədlərini aşa bilər, buna görə ağacdakı qiymətlər long long tipinə malikdir.

#define MAX 100010
long long SegTree[4 * MAX];

Summa funksiyası $[l e f t; r i g h t]$ [left; right] seqmentindəki elementlərin cəmini qaytarır. $v$ təpəsi $[l p os; r p os]$ [lpos; rpos] seqmentinə uyğun gəlir.

long long Summa(int v, int lpos, int rpos, int left, int right)
{

Əgər sorğu seqmenti boşdursa ( $l e f t > r i g h t$ left > right), $0$ qaytarılır — toplama üçün neytral element.

  if (left > right) return 0;

Əgər sorğu seqmenti $v$ təpəsinin $[l p os; r p os]$ [lpos; rpos] seqmenti ilə üst-üstə düşürsə, orada saxlanılan cəm qaytarılır.

  if ((left == lpos) && (right == rpos))
    return SegTree[v];

Əks halda seqmentin ortası tapılır $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Sorğu seqmenti iki hissəyə bölünür: $[l e f t; min (r i g h t, mi d)]$ [left; \min(right, mid)] sol övladın seqmentində yerləşir, $[max (l e f t, mi d + 1); r i g h t]$ [\max(left, mid + 1); right] isə sağ övladın seqmentində yerləşir. Hissələrdən biri boş ola bilər. Hər iki hissədəki cəmlər rekursiv şəkildə hesablanır və onların cəmi qaytarılır.

  return Summa(2*v, lpos, mid, left, min(right, mid)) +
         Summa(2*v+1, mid + 1, rpos, max(left, mid + 1), right);
}

update funksiyası $p os$ indeksli elementə $v a l$ qiymətini mənimsədir. $v$ təpəsi $[l p os; r p os]$ [lpos; rpos] seqmentinə uyğun gəlir.

void update(int v, int lpos, int rpos, int pos, int val)
{

Əgər $v$ təpəsinin seqmenti bir elementdən ibarətdirsə ( $l p os = r p os$ lpos = rpos), onda $v$ $p os$ mövqeyinə uyğun gələn yarpaqdır. Ona $v a l$ qiymətini yazın.

  if (lpos == rpos)
    SegTree[v] = val;
  else
  {

Əks halda, seqmentin hansı yarısında $p os$ mövqeyinin yerləşdiyi müəyyən edilir və rekursiv şəkildə sol və ya sağ övlada enilir.

    int mid = (lpos + rpos) / 2;
    if (pos <= mid) update(2*v, lpos, mid, pos, val);
    else update(2*v+1, mid + 1, rpos, pos, val);

Rekursiyadan qayıtdıqdan sonra $v$ təpəsindəki cəm yenidən hesablanır. Bu şəkildə yarpaqdan kökə qədər olan yoldakı bütün təpələr yenilənir.

    SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
  }
}

Proqramın əsas hissəsi. Başlanğıcda massivin bütün elementləri sıfırdır, buna görə seqment ağacındakı bütün cəmlər də sıfırdır. $S e g T r ee$ SegTree massivini sıfırlarla doldurun; ağacın ayrıca qurulmasına ehtiyac yoxdur.

memset(SegTree, 0, sizeof(SegTree));

Massivin ölçüsü $n$ və sorğuların sayı $k$ oxunur. Formatdakı \n simvolu sətir sonunu buraxır ki, növbəti oxunan simvol sorğu hərfi olsun.

scanf("%d %d\n", &n, &k);

$k$ sorğu bir-bir emal edilir. Əvvəlcə sorğu hərfi $co mman d$ oxunur. Əgər bu 'A'-dırsa, $i$ indeksli elementə $x$ qiyməti mənimsədilir. Əks halda $[l; r]$ [l; r] seqmentindəki cəm çap edilir. "%lld %lld\n" formatındakı \n simvolu sorğudan sonrakı sətir sonunu buraxır.

for (j = 0; j < k; j++)
{
  scanf("%c", &command);
  if (command == 'A')
  {
    scanf("%lld %lld\n", &i, &x);
    update(1, 1, n, i, x);
  }
  else
  {
    scanf("%lld %lld\n", &l, &r);
    printf("%lld\n", Summa(1, 1, n, l, r));
  }
}

C++

Alqoritmin tətbiqi — Fenvik ağacı

$M A X$ ölçülü $F e n w i c k$ Fenwick massivi Fenvik ağacını saxlayır. Qlobal massiv başlanğıcda sıfırlarla doldurulur ki, bu da başlanğıc sıfır massivinə uyğun gəlir.

#define MAX 100010
long long Fenwick[MAX];

Summma0_i funksiyası $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i prefiks cəmini qaytarır.

// Fenwick[0] + Fenwick[1] + ... + Fenwick[i]
long long Summma0_i(long long i)
{
  long long result = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    result += Fenwick[i];
  return result;
}

C++

IncElement funksiyası $a_{i}$ a_i elementinə $d e l t a$ əlavə edir. Elementlərin indeksləri $1$ -dən $n$ -ə qədərdir, buna görə dövr $i \leq n$ i \le n şərti ilə işləyir.

// Fenwick[i] = Fenwick[i] + delta
void IncElement(long long i, long long delta)
{
  for (; i <= n; i = (i | (i+1)))
    Fenwick[i] += delta;
}

Proqramın əsas hissəsi. Massivin ölçüsü $n$ və sorğuların sayı $k$ oxunur. Formatdakı \n simvolu sətir sonunu buraxır ki, növbəti oxunan simvol sorğu hərfi olsun.

scanf("%d %d\n",&n,&k);

$k$ sorğu bir-bir emal edilir. Əvvəlcə sorğu hərfi $co mman d$ oxunur.

for(j = 0; j < k; j++)
{
  scanf("%c",&command);

$A i x$ sorğusu. $a_{i}$ a_i elementinin cari qiyməti $s u m (i) - s u m (i - 1)$ sum(i) - sum(i - 1)-ə bərabərdir. Ona $x$ qiymətini mənimsətmək üçün $x$ $x - s u m (i) + s u m (i - 1)$ x - sum(i) + sum(i - 1) fərqi ilə əvəz olunur və IncElement funksiyası vasitəsilə $a_{i}$ a_i-yə əlavə edilir.

  if (command == 'A')
  {
    scanf("%lld %lld\n",&i,&x);
    x = x - Summma0_i(i) + Summma0_i(i-1);
    IncElement(i,x);

$Q l r$ sorğusu. $[l; r]$ [l; r] seqmentindəki cəm $s u m (r) - s u m (l - 1)$ sum(r) - sum(l - 1)-ə bərabərdir.

  } else
  {
    scanf("%lld %lld\n",&l,&r);
    printf("%lld\n",Summma0_i(r) - Summma0_i(l-1));
  }
}