Запросы суммы диапазонов — распространенная проблема в информатике и анализе данных, целью которой является эффективное вычисление суммы элементов в заданном диапазоне в массиве или последовательности. В этой статье мы рассмотрим различные методы обработки запросов суммы диапазона, попутно предоставляя примеры кода и разговорные пояснения. К концу вы получите четкое представление о различных методах вычисления диапазонов сумм и сможете оптимизировать свой код для повышения эффективности.

Метод 1: метод грубой силы
Самым простым методом вычисления запросов суммы диапазона является метод грубой силы. Он включает в себя перебор каждого элемента в заданном диапазоне и их суммирование. Несмотря на свою простоту, этот метод может оказаться неэффективным для больших массивов или частых запросов.

def range_sum_brute_force(arr, start, end):
    total = 0
    for i in range(start, end + 1):
        total += arr[i]
    return total

Метод 2: метод префиксной суммы
Метод префиксной суммы — популярный подход к оптимизации запросов суммы диапазона. Он включает в себя предварительное вычисление совокупной суммы элементов до каждого индекса массива. Таким образом, мы можем вычислить сумму в диапазоне, вычитая сумму префикса в начальном индексе из суммы префикса в конечном индексе.

def compute_prefix_sum(arr):
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]
    return prefix_sum
def range_sum_prefix_sum(prefix_sum, start, end):
    if start == 0:
        return prefix_sum[end]
    return prefix_sum[end] - prefix_sum[start - 1]

Метод 3: Структура данных дерева сегментов
Дерево сегментов представляет собой универсальную структуру данных, которая может эффективно обрабатывать запросы суммы диапазона. Он предполагает разделение массива на сегменты и сохранение суммы каждого сегмента в древовидной структуре. Этот метод позволяет нам вычислять суммы диапазонов с временной сложностью O(log n).

class SegmentTreeNode:
    def __init__(self, start, end, left=None, right=None):
        self.start = start
        self.end = end
        self.left = left
        self.right = right
        self.sum = 0
def build_segment_tree(arr, start, end):
    if start > end:
        return None
    if start == end:
        node = SegmentTreeNode(start, end)
        node.sum = arr[start]
        return node
    mid = (start + end) // 2
    left = build_segment_tree(arr, start, mid)
    right = build_segment_tree(arr, mid + 1, end)
    node = SegmentTreeNode(start, end)
    node.left = left
    node.right = right
    node.sum = left.sum + right.sum
    return node
def range_sum_segment_tree(node, start, end):
    if node.start == start and node.end == end:
        return node.sum
    mid = (node.start + node.end) // 2
    if end <= mid:
        return range_sum_segment_tree(node.left, start, end)
    if start > mid:
        return range_sum_segment_tree(node.right, start, end)
    return (
        range_sum_segment_tree(node.left, start, mid) +
        range_sum_segment_tree(node.right, mid + 1, end)
    )

Метод 4: двоичное индексированное дерево (дерево Фенвика)
Двоичное индексированное дерево, также известное как дерево Фенвика, является еще одной эффективной структурой данных для запросов суммы диапазона. Он позволяет как эффективно обновлять данные, так и вычислять суммы диапазонов с временной сложностью O(log n).

class FenwickTree:
    def __init__(self, n):
        self.tree = [0] * (n + 1)
    def update(self, idx, delta):
        while idx < len(self.tree):
            self.tree[idx] += delta
            idx += idx & -idx
    def query(self, idx):
        total = 0
        while idx > 0:
            total += self.tree[idx]
            idx -= idx & -idx
        return total
def build_fenwick_tree(arr):
    n = len(arr)
    fenwick_tree = FenwickTree(n)
    for i in range(n):
        fenwick_tree.update(i + 1, arr[i])
    return fenwick_tree
def range_sum_fenwick_tree(fenwick_tree, start, end):
    return fenwick_tree.query(end + 1) - fenwick_tree.query(start)

В этой статье мы рассмотрели несколько методов обработки запросов суммы диапазона. Мы начали с метода грубой силы и постепенно внедрили более эффективные методы, такие как метод суммы префиксов, деревья отрезков и деревья Фенвика. Каждый метод имеет свои преимущества и особенности, зависящие от конкретного варианта использования. Понимая эти методы, вы сможете выбрать наиболее подходящий подход для оптимизации вычисления запросов суммы диапазонов в вашем коде.