E113. Fenwick tree

e-maxx algorithm original: C/C++ #algorithm #data-structures #emaxx #fenwick-tree #range-query #tree

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

Static

Источник: e-maxx.ru/algo, страница PDF 355.

Fenwick tree - это структура данных, cây на mảngе, обладающее следующими свойствами: 1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N);

2) позволяет изменять значение любого elementа за O (log N);

3) требует O (N) памяти, а точнее, ровно столько же, сколько и mảng из N elementов; 4) легко обобщается на случай многомерных mảngов. Наиболее распространённое применение дерева Фенвика - для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk. Fenwick tree было впервые описано в статье "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).

Описание

Для простоты описания мы предполагаем, что операция G, по которой мы строим cây, - это сумма. Пусть дан mảng A[0..N-1]. Fenwick tree - mảng T[0..N-1], в каждом elementе которого хранится сумма некоторых elementов mảngа A:

Ti = сумма Aj для всех F(i) <= j <= i,

где F(i) - некоторая функция, которую мы определим несколько позже. Теперь мы уже можем написать псевдокод для функции вычисления суммы на отрезке [0; R] и для функции изменения ячейки:

int sum (int r)

{

int result = 0;

while (r >= 0) {

result += t[r];

r = f(r) - 1;

}

return result;

}

void inc (int i, int delta)

{

для всех j, для которых F(j) <= i <= j

{

t[j] += delta;

} } Функция sum работает следующим образом. Вместо того чтобы идти по всем elementам mảngа A, она движется по mảngу T, делая "прыжки" через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F(R); R], затем берёт сумму на отрезке [F(F(R)-1); F(R)-1], и так далее, пока не дойдёт до нуля. Функция inc движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы Tj только для тех позиций, для которых это нужно, т.е. для всех j, для которых F(j) <= i <= j. Очевидно, что от выбора функции F будет зависеть скорость выполнения обеих операций. Сейчас мы рассмотрим функцию, которая позволит достичь логарифмической производительности в обоих случаях. Определим значение F(X) следующим образом. Рассмотрим двоичную запись этого числа и посмотрим на его младший бит. Если он равен нулю, то F(X) = X. Иначе двоичное представление числа X оканчивается на группу из одной или нескольких единиц. Заменим все единицы из этой группы на нули, и присвоим полученное number значению функции F(X). Этому довольно сложному описанию соответствует очень простая формула:

F(X) = X & (X+1),

где & - это операция побитового логического "И". Нетрудно убедиться, что эта формула соответствует словесному описанию функции, данному выше.

Нам осталось только научиться быстро находить такие числа j, для которых F(j) <= i <= j. Однако нетрудно убедиться в том, что все такие числа j получаются из i последовательными заменами самого правого (самого младшего) нуля в двоичном представлении. НаVí dụ, для i = 10 мы получим, что j = 11, 15, 31, 63 и т.д. Как ни странно, такой операции (замена самого младшего нуля на единицу) также соответствует очень простая формула:

H(X) = X | (X+1),

где | - это операция побитового логического "ИЛИ".

Cài đặt дерева Фенвика для суммы для

одномерного случая

vector<int> t;

int n;

void init (int nn)

{

n = nn;

t.assign (n, 0);

}

int sum (int r)

{

int result = 0;

for (; r >= 0; r = (r & (r+1)) - 1)

result += t[r];

return result;

}

void inc (int i, int delta)

{

for (; i < n; i = (i | (i+1)))

t[i] += delta;

}

int sum (int l, int r)

{

return sum (r) - sum (l-1);

}

void init (vector<int> a)

{

init ((int) a.size());

for (unsigned i = 0; i < a.size(); i++)

inc (i, a[i]);

}

Cài đặt дерева Фенвика для минимума

для одномерного случая

Следует сразу заметить, что, поскольку Fenwick tree позволяет find значение функции в произвольном отрезке [0; R], то мы никак не сможем find минимум на отрезке [L;R], где L > 0. Далее, все изменения значений должны происходить только в сторону уменьшения (опять же, поскольку никак не получится обратить функцию min). Это значительные Ràng buộc.

vector<int> t;

int n;

const int INF = 100010001000;

void init (int nn)

{

n = nn;

t.assign (n, INF);

}

int getmin (int r)

{

int result = INF;

for (; r >= 0; r = (r & (r+1)) - 1)

result = min (result, t[r]);

return result;

}

void update (int i, int new_val)

{

for (; i < n; i = (i | (i+1)))

t[i] = min (t[i], new_val);

}

void init (vector<int> a)

{

init ((int) a.size());

for (unsigned i = 0; i < a.size(); i++)

update (i, a[i]);

}

Cài đặt дерева Фенвика для суммы для

двумерного случая

Как уже отмечалось, Fenwick tree легко обобщается на многомерный случай.

vector <vector <int> > t;

int n, m;

int sum (int x, int y)

{

int result = 0;

for (int i = x; i >= 0; i = (i & (i+1)) - 1)

for (int j = y; j >= 0; j = (j & (j+1)) - 1)

result += t[i][j];

return result;

}

void inc (int x, int y, int delta)

{

for (int i = x; i < n; i = (i | (i+1)))

for (int j = y; j < m; j = (j | (j+1)))

t[i][j] += delta;

}

C# lời giải

bản nháp tự động, xem lại trước khi gửi

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    Ti = сумма Aj для всех F(i) <= j <= i,
    int sum (int r)
    {
            int result = 0;
            while (r >= 0) {
                    result += t[r];
                    r = f(r) - 1;
            }
            return result;
    }
    void inc (int i, int delta)
    {
            для всех j, для которых F(j) <= i <= j
            {
                    t[j] += delta;
            }
    }
    F(X) = X & (X+1),
    H(X) = X | (X+1),
    List<int> t;
    int n;
    void init (int nn)
    {
            n = nn;
            t.assign (n, 0);
    }
    int sum (int r)
    {
            int result = 0;
            for (; r >= 0; r = (r & (r+1)) - 1)
                    result += t[r];
            return result;
    }
    void inc (int i, int delta)
    {
            for (; i < n; i = (i | (i+1)))
                    t[i] += delta;
    }
    int sum (int l, int r)
    {
            return sum (r) - sum (l-1);
    }
    void init (List<int> a)
    {
            init ((int) a.size());
            for (unsigned i = 0; i < a.size(); i++)
                    inc (i, a[i]);
    }
    List<int> t;
    int n;
    const int INF = 1000*1000*1000;
    void init (int nn)
    {
            n = nn;
            t.assign (n, INF);
    }
    int getmin (int r)
    {
            int result = INF;
            for (; r >= 0; r = (r & (r+1)) - 1)
                    result = min (result, t[r]);
            return result;
    }
    void update (int i, int new_val)
    {
            for (; i < n; i = (i | (i+1)))
                    t[i] = min (t[i], new_val);
    }
    void init (List<int> a)
    {
            init ((int) a.size());
            for (unsigned i = 0; i < a.size(); i++)
                    update (i, a[i]);
    }
    vector <vector <int> > t;
    int n, m;
    int sum (int x, int y)
    {
            int result = 0;
            for (int i = x; i >= 0; i = (i & (i+1)) - 1)
                    for (int j = y; j >= 0; j = (j & (j+1)) - 1)
                            result += t[i][j];
            return result;
    }
    void inc (int x, int y, int delta)
    {
            for (int i = x; i < n; i = (i | (i+1)))
                    for (int j = y; j < m; j = (j | (j+1)))
                            t[i][j] += delta;
    }
}

C++ lời giải

đã khớp/gốc

Ti = сумма Aj для всех F(i) <= j <= i,
int sum (int r)
{
        int result = 0;
        while (r >= 0) {
                result += t[r];
                r = f(r) - 1;
        }
        return result;
}
void inc (int i, int delta)
{
        для всех j, для которых F(j) <= i <= j
        {
                t[j] += delta;
        }
}
F(X) = X & (X+1),
H(X) = X | (X+1),
vector<int> t;
int n;
void init (int nn)
{
        n = nn;
        t.assign (n, 0);
}
int sum (int r)
{
        int result = 0;
        for (; r >= 0; r = (r & (r+1)) - 1)
                result += t[r];
        return result;
}
void inc (int i, int delta)
{
        for (; i < n; i = (i | (i+1)))
                t[i] += delta;
}
int sum (int l, int r)
{
        return sum (r) - sum (l-1);
}
void init (vector<int> a)
{
        init ((int) a.size());
        for (unsigned i = 0; i < a.size(); i++)
                inc (i, a[i]);
}
vector<int> t;
int n;
const int INF = 1000*1000*1000;
void init (int nn)
{
        n = nn;
        t.assign (n, INF);
}
int getmin (int r)
{
        int result = INF;
        for (; r >= 0; r = (r & (r+1)) - 1)
                result = min (result, t[r]);
        return result;
}
void update (int i, int new_val)
{
        for (; i < n; i = (i | (i+1)))
                t[i] = min (t[i], new_val);
}
void init (vector<int> a)
{
        init ((int) a.size());
        for (unsigned i = 0; i < a.size(); i++)
                update (i, a[i]);
}
vector <vector <int> > t;
int n, m;
int sum (int x, int y)
{
        int result = 0;
        for (int i = x; i >= 0; i = (i & (i+1)) - 1)
                for (int j = y; j >= 0; j = (j & (j+1)) - 1)
                        result += t[i][j];
        return result;
}
void inc (int x, int y, int delta)
{
        for (int i = x; i < n; i = (i | (i+1)))
                for (int j = y; j < m; j = (j | (j+1)))
                        t[i][j] += delta;
}

Java lời giải

bản nháp tự động, xem lại trước khi gửi

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    Ti = сумма Aj для всех F(i) <= j <= i,
    int sum (int r)
    {
            int result = 0;
            while (r >= 0) {
                    result += t[r];
                    r = f(r) - 1;
            }
            return result;
    }
    void inc (int i, int delta)
    {
            для всех j, для которых F(j) <= i <= j
            {
                    t[j] += delta;
            }
    }
    F(X) = X & (X+1),
    H(X) = X | (X+1),
    ArrayList<Integer> t;
    int n;
    void init (int nn)
    {
            n = nn;
            t.assign (n, 0);
    }
    int sum (int r)
    {
            int result = 0;
            for (; r >= 0; r = (r & (r+1)) - 1)
                    result += t[r];
            return result;
    }
    void inc (int i, int delta)
    {
            for (; i < n; i = (i | (i+1)))
                    t[i] += delta;
    }
    int sum (int l, int r)
    {
            return sum (r) - sum (l-1);
    }
    void init (ArrayList<Integer> a)
    {
            init ((int) a.size());
            for (unsigned i = 0; i < a.size(); i++)
                    inc (i, a[i]);
    }
    ArrayList<Integer> t;
    int n;
    const int INF = 1000*1000*1000;
    void init (int nn)
    {
            n = nn;
            t.assign (n, INF);
    }
    int getmin (int r)
    {
            int result = INF;
            for (; r >= 0; r = (r & (r+1)) - 1)
                    result = min (result, t[r]);
            return result;
    }
    void update (int i, int new_val)
    {
            for (; i < n; i = (i | (i+1)))
                    t[i] = min (t[i], new_val);
    }
    void init (ArrayList<Integer> a)
    {
            init ((int) a.size());
            for (unsigned i = 0; i < a.size(); i++)
                    update (i, a[i]);
    }
    vector <vector <int> > t;
    int n, m;
    int sum (int x, int y)
    {
            int result = 0;
            for (int i = x; i >= 0; i = (i & (i+1)) - 1)
                    for (int j = y; j >= 0; j = (j & (j+1)) - 1)
                            result += t[i][j];
            return result;
    }
    void inc (int x, int y, int delta)
    {
            for (int i = x; i < n; i = (i | (i+1)))
                    for (int j = y; j < m; j = (j | (j+1)))
                            t[i][j] += delta;
    }
}

Материал разбит как Thuật toánическая Bài toán: изучить постановку, понять асимптотику и реализовать Thuật toán на выбранном языке.

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.