html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Дерево Фенвика с модификацией на отрезке

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

1. Постановка задачи


Имеется массив. Необходимо уметь выполнять запросы двух видов:
  1. Модификация — прибавить d к каждому элементу отрезка [l, r]
  2. Сумма — вычислить сумму элементов отрезка [l, r]

2. Описание решения


Нетрудно заметить, что оба вида запросов можно «облегчить» до отрезка [0, r], разбивая отрезок [l, r] на два префикса. Как и для дерева отрезков, заведём второй массив, в котором будем хранить сколько надо прибавить ко всем числам этого отрезка.

Создадим класс Fenwick с прототипами будущих методов.

class Fenwick{
  int *m, *mt, N;
public:
  Fenwick(int n);
  Fenwick(int a[], int n);
  void add_range(int r, int d);
  void add_range(int l, int r, int d);
  int sum(int r);
  int sum(int l, int r);
};


В первом конструкторе достаточно выделить память и обнулить элементы массива. А во втором ещё пройдёмся по массиву a и прорелаксируем значения в дереве.

Fenwick::Fenwick(int n){
  N = n;
  m = new int[N];
  mt = new int[N];
  memset(m, 0, sizeof(int)*N);
  memset(mt, 0, sizeof(int)*N);
}
Fenwick::Fenwick(int a[], int n){
  N = n;
  m = new int[N];
  mt = new int[N];
  memset(m, 0, sizeof(int)*N);
  memset(mt, 0, sizeof(int)*N);
  for(int i=0;i<N;++i){
    m[i] += a[i];
    if((i|(i+1))<N) m[i|(i+1)] += m[i];
  }
}


Рассмотрим теперь операцию изменения. Предположим пришёл запрос «прибавить 1 к элементам отрезка [0, 9]». Этот отрезок полностью покрывается непересекающимися отрезками [0, 7] и [8, 9], поэтому в 7 и 9 элементы массива mt прибавляем 1. Но есть отрезки, содержащие [0, 9] (или его часть) в качестве подотрезка. Все они располагаются справа. Для них необходимо изменить значение в массиве m на столько, сколько элементов отрезка [0, 9] они содержат. То есть в m[11] прибавить 2, а к m[15] — 10.



Из рисунка видно, что перемещения происходят по тем же законам, что и в тривиальной реализации дерева Фенвика, поэтому сразу перейдём к коду.

void Fenwick::add_range(int r, int d){
  if(r<0) return ;
  for(int i=r;i>=0;i=(i&(i+1))-1) mt[i] += d;
  for(int i=r|(r+1);i<N;i|=i+1) m[i] += d*(r-(i&(i+1))+1);
}
void Fenwick::add_range(int l, int r, int d){
  add_range(r, d);
  add_range(l-1, -d);
}


Для суммы на префиксе подойдёт та же картинка с тем лишь пояснением, что для зелёных элементов необходимо прибавить и m, и mt, а для синих только mt (то есть учесть большие накрывающие отрезки).

int Fenwick::sum(int r){
  if(r<0) return 0;
  int res = 0;
  for(int i=r;i>=0;i=(i&(i+1))-1) res += m[i] + mt[i]*(i-(i&(i+1))+1);
  for(int i=r|(r+1);i<N;i|=i+1) res += mt[i]*(r-(i&(i+1))+1);
  return res;
}
int Fenwick::sum(int l, int r){
  return sum(r) - sum(l-1);
}

3. Итоги


Нам удалось получить структуру данных с инициализацией за O(N), модификацией и суммой на отрезке за O(logN). На рандомном тесте с 10000000 элементов и 10000000 запросов получил такие цифры:
Структура данных Инициализация Модификация Сумма
Fenwick 0.13 с 9.12 с 8.90 с
RSQ (реализация с e-maxx) 0.25 с 17.13 с 13.53 с
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

1

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции