Aralık Güncellemeleri için Fark Dizileri

Prefix toplamları aralık sorgularını hızlıca yanıtladı. Bir fark dizisi ise bunu tersine çevirerek çok sayıda aralık güncellemesini hızlıca uygulamanızı sağlar. 🔁

Bir aralıktaki her öğeye bir değer eklemek ve bunu birçok kez tekrarlamak, her güncelleme için O(n) işlem gerektirir. q güncelleme boyunca bu maliyet hızla büyür.

Her hücreye dokunmak yerine yalnızca değişikliğin nerede başladığını ve nerede bittiğini kaydedin. Ortayı değil, kenarları işaretleyin.

Bir fark dizisi, her öğeyle ondan önce gelen öğe arasındaki farkı saklar. Tek bir farkı değiştirmek, ilerideki bütün bir bölümü kaydırır.

l ile r arasına v eklemek için l dizinine v ekleyin ve r + 1 dizininden v çıkarın. Yalnızca iki değişiklik tüm aralığı kapsar.

l konumundaki artı işareti değişikliği başlatır; r + 1 konumundaki eksi işareti ise yeniden kapatır. Birlikte güncellemeyi tek bir aralıkla sınırlarlar.

Her güncelleme yalnızca iki dizi yazma işleminden oluştuğu için q güncelleme toplamda O(q) sürer. Asıl işlem sona ertelenir.

Tüm işaretleri yerleştirdikten sonra fark dizisinin prefix toplamını alın. Bu tek geçiş, tüm son değerleri yeniden oluşturur.

Diziyi bir hücre daha uzun oluşturun; böylece r + 1 hiçbir zaman dizinin sonunu aşmaz. Bu ek koruma hücresi, dizin hatalarını önler.

Güncellemeleri işaretlemek için O(q), diziyi yeniden oluşturmak için de bir O(n) geçiş harcarsınız. Birleşik maliyet, basit O(n çarpı q) yönteminden çok daha düşüktür.

Fark dizileri, rezervasyon sayılarını, yol geçiş ücretlerini ve çok sayıda aralık ekleme işlemiyle tek bir son okuma içeren her problemi çözmede çok etkilidir.

l dizininden r dizinine kadar her öğeye v ekliyorsunuz.

Bir fark dizisiyle aralık güncellemelerini toplu olarak uygulayabilirsiniz: l ile r + 1 konumlarını işaretleyin, ardından yeniden oluşturmak için bir kez prefix toplamı alın. Hızlı güncellemeler, tek okuma. ✅