Dima və massiv#2941

Dima və massiv (Həll təhlili)

Məsələ iki tip əməliyyatın emalını tələb edir:

massivin bir elementinə qiymət mənimsətmək;
$[f; t]$ seqmentindəki elementlərin cəmini hesablamaq.

Bizə hər iki əməliyyatı sürətlə yerinə yetirən bir verilənlər strukturu lazımdır. Belə bir struktur cəmlər üçün seqment ağacıdır. 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əm seqmentdəki cəmi hesablamağa, həm də massivin elementini $O (lo g n)$ O(\log n) vaxtında dəyişməyə imkan verir.

Misal

Nümunədəki sorğuları simulyasiya edək. Əvvəlcə massiv $(1, 2, 3)$ (1, 2, 3)-dir.

$? 13$ : $[1; 3]$ seqmentindəki elementlərin cəmi $1 + 2 + 3 = 6$ 1 + 2 + 3 = 6-dır;
$= 32$ : $a_{3}$ a_3 elementinə $2$ qiyməti mənimsədilir və massiv $(1, 2, 2)$ (1, 2, 2) olur;
$? 13$ : $[1; 3]$ seqmentindəki elementlərin cəmi $1 + 2 + 2 = 5$ 1 + 2 + 2 = 5-dir.

Seqment ağacının necə dəyişdiyinə baxaq. Solda ilkin massiv üçün ağac, sağda isə $a_{3} = 2$ a_3 = 2 mənimsəməsindən sonrakı ağac göstərilib. Hər təpədə onun seqmenti və bu seqmentdəki elementlərin cəmi göstərilib; dəyişən təpələr işıqlandırılıb.

Hər iki sorğunun $[1; 3]$ seqmenti kökün seqmenti ilə üst-üstə düşür, buna görə cavab birbaşa kökdən götürülür: mənimsəmədən əvvəl $6$ , sonra isə $5$ . $a_{3} = 2$ a_3 = 2 mənimsəməsi zamanı yalnız $[3]$ yarpağından kökə qədər olan yoldakı təpələr yenidən hesablanır: $[3]$ yarpağı $2$ qiymətini alır, kök isə $3 + 2 = 5$ 3 + 2 = 5 qiymətini alır.

Alqoritmin realizasiyası

Seqment ağacını uzunluğu $4 \cdot M A X$ 4 \cdot MAX olan $S e g T r ee$ SegTree vektorunda saxlayaq, burada $M A X = 5 \cdot 1 0^{5}$ MAX = 5 \cdot 10^5 massiv elementlərinin maksimum sayıdır. Ağacın hər bir təpəsi öz seqmentinin elementlərinin cəmini saxlayır.

#define MAX 500000
vector<int> SegTree(4*MAX,0);

BuildTree funksiyası $a$ massivindən seqment ağacını qurur. O, cari təpənin nömrəsi $v$ və bu təpəyə uyğun gələn seqmentin $l p os$ və $r p os$ sərhədlərini qəbul edir.

void BuildTree(vector<int>&a, int v, int lpos, int rpos)
{

Əgər $v$ təpəsinin seqmenti bir elementdən ibarətdirsə ( $l p os = r p os$ lpos = rpos), onda $v$ ağacın yarpağıdır. Ona $a [l p os]$ qiymətini yazırıq.

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

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

    int mid = (lpos + rpos) / 2;

$[l p os; r p os]$ [lpos; rpos] seqmenti iki alt-seqmentə bölünür: $[l p os; mi d]$ [lpos; mid] və $[mi d + 1; r p os]$ [mid + 1; rpos]. Sol övlad $2 v$ və sağ övlad $2 v + 1$ 2v + 1 üçün ağacı rekursiv şəkildə quraq.

    BuildTree(a, 2*v, lpos, mid);
    BuildTree(a, 2*v+1, mid + 1, rpos);

$v$ təpəsindəki qiymət onun övladlarının qiymətlərinin cəminə bərabərdir.

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

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əsi yarpaqdırsa ( $l p os = r p os$ lpos = rpos), o, $p os$ mövqeyinə uyğun gəlir. Ona $v a l$ qiymətini yazırıq.

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

Əks halda, seqmentin hansı yarısında $p os$ mövqeyinin olduğunu müəyyən edirik və rekursiv şəkildə sol və ya sağ övlada enirik.

    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əmi yenidən hesablayırıq. 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];
  }
}

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. Ə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.

int Summa(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;

Əgər sorğu seqmenti təpənin seqmenti ilə üst-üstə düşürsə, cavab $S e g T r ee [v]$ SegTree[v]-də saxlanılır.

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

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

  int mid = (lpos + rpos) / 2;

Sorğu seqmentini iki hissəyə bölək: $[l e f t; min (r i g h t, mi d)]$ [left; \min(right, mid)] sol övladın seqmentində, $[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 övlad üçün nəticələrin cəmini qaytarırıq.

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

Proqramın əsas hissəsi. Massivin ölçüsünü $n$ -i, sorğuların sayını $q$ -nu və massivin elementlərini $v$ vektoruna, $1$ -ci indeksdən başlayaraq oxuyuruq. scanf("\n") çağırışı massivdən sonrakı sətir sonu simvolunu ötürür ki, növbəti oxunan simvol əməliyyat işarəsi olsun.

scanf("%d %d",&n,&q);
v.resize(n+1);
for(i = 1; i <= n; i++)
  scanf("%d",&v[i]);
scanf("\n");

$v [1 \dots n]$ v[1 \ldots n] elementlərindən seqment ağacını quraq.

BuildTree(v,1,1,n);

$q$ sorğusunu bir-bir emal edək. Əvvəlcə $c$ əməliyyat simvolunu oxuyuruq; "%c " formatındakı boşluq ondan sonrakı boşluğu ötürür. Əgər $c$ = '=' olarsa, $i$ indeksli elementə $d$ qiymətini mənimsədirik. Əks halda, $[f; t]$ seqmentindəki cəmi hesablayıb çap edirik. "%d %d\n" formatındakı \n simvolu sətir sonunu ötürür ki, növbəti dəfə $c$ -yə oxunan növbəti əməliyyatın işarəsi olsun.

for(j = 0; j < q; j++)
{
  scanf("%c ",&c);
  if (c == '=')
  {
    scanf("%d %d\n",&i,&d);
    Update(1,1,n,i,d);
  } else
  {
    scanf("%d %d\n",&f,&t);
    printf("%d\n",Summa(1,1,n,f,t));
  }
}

C++