Bir aralıktaki toplam (Editoryal)

Problem, iki tür sorguyu işlemeyi gerektiriyor: bir dizi elemanına bir değer atama ve $[l; r]$ [l; r] aralığındaki elemanların toplamını hesaplama. Eğer yalnızca dizinin kendisini saklarsak, bir atama $O (1)$ sürer, ancak her toplam sorgusu $O (n)$ işlem gerektirir. Önek toplamlarını saklarsak, bir toplam $O (1)$ sürede hesaplanır, ancak her atama $O (n)$ önek toplamının yeniden hesaplanmasını gerektirir. Sorgu sayısı büyük olduğunda, her iki yaklaşım da çok yavaş kalır.

Toplamlar için bir segment ağacı kullanıyoruz. Ağacın her bir düğümü kendi aralığındaki elemanların toplamını saklar ve bir iç düğümdeki değer, iki çocuğunun değerlerinin toplamına eşittir. Segment ağacı her iki işlemi de $O (lo g n)$ O(\log n) sürede gerçekleştirir. Bir toplam hesaplanırken, aralığın boş kısmı $0$ 'a karşılık gelir — toplama işlemi için nötr eleman.

Başlangıçta tüm dizi elemanları sıfırdır, bu yüzden ağacın tüm düğümlerindeki toplamlar da sıfırdır. Ağaç dizisini sıfırlarla doldurmak yeterlidir; ağacın ayrıca inşa edilmesine gerek yoktur.

Elemanların değerleri $1 0^{9}$ 10^9'a ulaşabilir, bu yüzden bir aralıktaki toplam $1 0^{5} \cdot 1 0^{9} = 1 0^{14}$ 10^5 \cdot 10^9 = 10^{14}'e ulaşabilir ve int türüne sığmaz. Ağaçtaki değerler long long türünde saklanır.

Şimdi Fenwick ağacı kullanan bir çözümü ele alalım. Her biri $O (lo g n)$ O(\log n) sürede gerçekleştirilen iki işlemi destekler:

$a_{i}$ a_i elemanına $d e l t a$ sayısını eklemek;
$s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i önek toplamını hesaplamak.

Başlangıçta tüm dizi elemanları sıfırdır, bu yüzden sıfırlarla doldurulmuş bir Fenwick ağacı zaten başlangıç dizisine karşılık gelir. Sorgulardaki indeksler $1$ 'den $n$ 'ye kadar değişir; $a_{0}$ a_0 elemanı kullanılmaz ve her zaman sıfırdır.

Atama. Bir Fenwick ağacı yalnızca bir elemana bir sayı ekleyebilir, ancak ona yeni bir değer atayamaz. Ancak bir elemanın mevcut değeri önek toplamları aracılığıyla hesaplanabilir:

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

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

Bu yüzden, $a_{i} = x$ a_i = x ataması, $a_{i}$ a_i'ye yeni ve eski değerler arasındaki farkı eklemekle değiştirilir:

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)

Aralık üzerinde toplam. $[l; r]$ [l; r] aralığındaki elemanların toplamı, iki önek toplamının farkına eşittir:

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)

Elemanların değerleri $1 0^{9}$ 10^9'a ulaşabilir, bu yüzden toplamlar $1 0^{14}$ 10^{14}'e ulaşabilir ve long long türünde saklanır.

Örnek

Başlangıçta dizi sıfırlardan oluşur. $A 22$ , $A 31$ ve $A 42$ sorgularından sonra, dizi $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0) haline gelir. Bunun için segment ağacı aşağıda gösterilmiştir. Her düğüm kendi aralığını ve o aralıktaki elemanların toplamını gösterir.

$A 31$ sorgusu yürütüldüğünde, yalnızca $[3]$ yaprağından köke giden yol üzerindeki düğümler yeniden hesaplanır: $[3]$ yaprağı $1$ değerini alır, $[1; 3]$ düğümü — $2 + 1 = 3$ 2 + 1 = 3 değerini, ve $[1; 5]$ kökü — $3 + 2 = 5$ 3 + 2 = 5 değerini alır.

$Q 11$ , $Q 22$ , $Q 33$ , $Q 44$ ve $Q 55$ sorguları yaprakların değerlerini döndürür: $0, 2, 1, 2, 0$ 0, 2, 1, 2, 0. $Q 15$ sorgusunun aralığı kökün aralığıyla aynıdır, bu yüzden cevap doğrudan kökten alınır ve $5$ 'e eşittir (vurgulanmış düğüm).

Örnekteki sorguları Fenwick ağacı kullanarak simüle edelim, $n = 5$ n = 5. Başlangıçta dizi $(0, 0, 0, 0, 0)$ (0, 0, 0, 0, 0)'dır. Her atama sorgusu için, tablo elemanın eski değerinin nasıl hesaplandığını ve hangi sayının eklendiğini gösterir; her toplam sorgusu için, önek toplamlarının farkını gösterir.

sorgu	hesaplama	sonuç
$A 22$	eski değer $s u m (2) - s u m (1) = 0 - 0 = 0$ sum(2) - sum(1) = 0 - 0 = 0, eklenen $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 0, 0, 0)$ (0, 2, 0, 0, 0)
$A 31$	eski değer $s u m (3) - s u m (2) = 2 - 2 = 0$ sum(3) - sum(2) = 2 - 2 = 0, eklenen $1 - 0 = 1$ 1 - 0 = 1	$(0, 2, 1, 0, 0)$ (0, 2, 1, 0, 0)
$A 42$	eski değer $s u m (4) - s u m (3) = 3 - 3 = 0$ sum(4) - sum(3) = 3 - 3 = 0, eklenen $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$

Örneğin, $Q 44$ sorgusundan önce dizi $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0)'dır, bu yüzden $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, ve cevap $5 - 3 = 2$ 5 - 3 = 2'dir.

Örnekte, tüm atamalar sıfır elemanlara uygulanmıştır. Tekrarlanan bir atama ile ne olacağını görelim, örneğin sonunda $A 35$ . Eski değer $s u m (3) - s u m (2) = 3 - 2 = 1$ sum(3) - sum(2) = 3 - 2 = 1'dir, bu yüzden $a_{3}$ a_3'e $5 - 1 = 4$ 5 - 1 = 4 eklenir ve eleman $5$ olur.

Algoritma uygulaması

Segment ağacı, uzunluğu $4 \cdot M A X$ 4 \cdot MAX olan $S e g T r ee$ SegTree dizisinde saklanır, burada $M A X$ dizi elemanlarının maksimum sayısıdır. Bir aralıktaki toplam int türünün sınırlarını aşabilir, bu yüzden ağaçtaki değerler long long türündedir.

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

Summa fonksiyonu, $[l e f t; r i g h t]$ [left; right] aralığındaki elemanların toplamını döndürür. $v$ düğümü $[l p os; r p os]$ [lpos; rpos] aralığına karşılık gelir.

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

Sorgu aralığı boşsa ( $l e f t > r i g h t$ left > right), $0$ döndür — toplama işlemi için nötr eleman.

  if (left > right) return 0;

Sorgu aralığı $v$ düğümünün $[l p os; r p os]$ [lpos; rpos] aralığıyla aynıysa, onda saklanan toplamı döndür.

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

Aksi takdirde, aralığın ortasını bul: $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Sorgu aralığını iki parçaya böl: $[l e f t; min (r i g h t, mi d)]$ [left; \min(right, mid)] sol çocuğun aralığında, $[max (l e f t, mi d + 1); r i g h t]$ [\max(left, mid + 1); right] sağ çocuğun aralığında yer alır. Parçalardan biri boş olabilir. Her iki parçadaki toplamları özyinelemeli olarak hesapla ve toplamlarını döndür.

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

update fonksiyonu, $p os$ indeksli elemana $v a l$ değerini atar. $v$ düğümü $[l p os; r p os]$ [lpos; rpos] aralığına karşılık gelir.

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

$v$ düğümünün aralığı tek bir elemandan oluşuyorsa ( $l p os = r p os$ lpos = rpos), o zaman $v$ , $p os$ konumuna karşılık gelen yapraktır. İçine $v a l$ değerini yaz.

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

Aksi takdirde, aralığın hangi yarısının $p os$ konumunu içerdiğini belirle ve özyinelemeli olarak sol veya sağ çocuğa in.

    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);

Özyinelemeden döndükten sonra, $v$ düğümündeki toplamı yeniden hesapla. Bu şekilde, yapraktan köke giden yol üzerindeki tüm düğümler güncellenir.

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

Programın ana bölümü. Başlangıçta tüm dizi elemanları sıfırdır, bu yüzden segment ağacındaki tüm toplamlar da sıfırdır. $S e g T r ee$ SegTree dizisini sıfırlarla doldur; ağacın ayrıca inşa edilmesine gerek yoktur.

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

Dizinin boyutu $n$ 'i ve sorgu sayısı $k$ 'yı oku. Formattaki \n karakteri satır sonunu atlar, böylece okunacak bir sonraki karakter sorgu harfi olur.

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

$k$ sorguyu birer birer işle. İlk önce sorgu harfi $co mman d$ 'ı oku. Eğer 'A' ise, $i$ indeksli elemana $x$ değerini ata. Aksi takdirde, $[l; r]$ [l; r] aralığındaki toplamı yazdır. "%lld %lld\n" formatındaki \n karakteri sorgudan sonraki satır sonunu atlar.

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++

Algoritma uygulaması — Fenwick ağacı

$M A X$ boyutundaki $F e n w i c k$ Fenwick dizisi, Fenwick ağacını saklar. Global bir dizi başlangıçta sıfırlarla doldurulur, bu da başlangıç sıfır dizisine karşılık gelir.

#define MAX 100010
long long Fenwick[MAX];

Summma0_i fonksiyonu, $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i önek toplamını döndürü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 fonksiyonu, $a_{i}$ a_i elemanına $d e l t a$ ekler. Elemanların indeksleri $1$ 'den $n$ 'ye kadar değişir, bu yüzden döngü $i \leq n$ i \le n olduğu sürece çalışır.

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

Programın ana bölümü. Dizinin boyutu $n$ 'i ve sorgu sayısı $k$ 'yı oku. Formattaki \n karakteri satır sonunu atlar, böylece okunacak bir sonraki karakter sorgu harfi olur.

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

$k$ sorguyu birer birer işle. İlk önce sorgu harfi $co mman d$ 'ı oku.

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

$A i x$ sorgusu. $a_{i}$ a_i elemanının mevcut değeri $s u m (i) - s u m (i - 1)$ sum(i) - sum(i - 1)'e eşittir. Ona $x$ değerini atamak için, $x$ 'i $x - s u m (i) + s u m (i - 1)$ x - sum(i) + sum(i - 1) farkıyla değiştir ve bunu IncElement fonksiyonunu kullanarak $a_{i}$ a_i'ye ekle.

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

$Q l r$ sorgusu. $[l; r]$ [l; r] aralığındaki toplam $s u m (r) - s u m (l - 1)$ sum(r) - sum(l - 1)'e eşittir.

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