Иногда я задумываюсь, какую реализацию дерева отрезков написать в задаче. Обычно я при помощи метода "пальцем в небо" выбираю какую-то и в большинстве случаев она проходит ограничения.

Я решил подвести основу, так сказать базу, под этот выбор и протестировал на производительность 4 разные реализации:

• Простой рекурсивный "Разделяй и властвуй"
  Код

  struct SimpleRecursiveSegmentTree {
      unsigned size;
  
    private:
      std::vector<long long> t;
  
      void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {
          if (r == l + 1) {
              t[p] = v[l];
              return;
          }
          unsigned m = (l + r) / 2;
          _build(v, 2 * p + 1, l, m);
          _build(v, 2 * p + 2, m, r);
          t[p] = t[2 * p + 1] + t[2 * p + 2];
      }
  
      long long _get(unsigned p, unsigned l, unsigned r, unsigned a,
                     unsigned b) const {
          if (b <= l || r <= a) {
              return 0LL;
          }
          if (a <= l && r <= b) {
              return t[p];
          }
          unsigned m = (l + r) / 2;
          return _get(2 * p + 1, l, m, a, b) + _get(2 * p + 2, m, r, a, b);
      }
  
      void _add(unsigned p, unsigned l, unsigned r, unsigned i, int x) {
          if (i < l || r <= i) {
              return;
          }
          if (r == l + 1) {
              t[p] += x;
              return;
          }
          unsigned m = (l + r) / 2;
          _add(2 * p + 1, l, m, i, x);
          _add(2 * p + 2, m, r, i, x);
          t[p] = t[2 * p + 1] + t[2 * p + 2];
      }
  
    public:
      SimpleRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {
          t.resize(4 * size);
      }
  
      SimpleRecursiveSegmentTree(const std::vector<int> &v) noexcept
          : size(v.size()) {
          t.resize(4 * size);
          _build(v, 0, 0, size);
      }
  
      void add(unsigned i, int x) { _add(0, 0, size, i, x); }
  
      long long get(unsigned l, unsigned r) const {
          return _get(0, 0, size, l, r);
      }
  };
  

• Оптимизированный рекурсивный "Разделяй и властвуй", который не спускается в заведомо ненужных сыновей.
  Код

  struct OptimizedRecursiveSegmentTree {
      unsigned size;
  
    private:
      std::vector<long long> t;
  
      void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {
          if (r == l + 1) {
              t[p] = v[l];
              return;
          }
          unsigned m = (l + r) / 2;
          _build(v, 2 * p + 1, l, m);
          _build(v, 2 * p + 2, m, r);
          t[p] = t[2 * p + 1] + t[2 * p + 2];
      }
  
      long long _get(unsigned p, unsigned l, unsigned r, unsigned a,
                     unsigned b) const {
          if (a <= l && r <= b) {
              return t[p];
          }
          unsigned m = (l + r) / 2;
          long long res = 0;
          if (a < m) {
              res += _get(2 * p + 1, l, m, a, b);
          }
          if (b > m) {
              res += _get(2 * p + 2, m, r, a, b);
          }
          return res;
      }
  
      void _add(unsigned p, unsigned l, unsigned r, unsigned i, int x) {
          if (r == l + 1) {
              t[p] += x;
              return;
          }
          unsigned m = (l + r) / 2;
          if (i < m) {
              _add(2 * p + 1, l, m, i, x);
          } else {
              _add(2 * p + 2, m, r, i, x);
          }
          t[p] = t[2 * p + 1] + t[2 * p + 2];
      }
  
    public:
      OptimizedRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {
          t.resize(4 * size);
      }
  
      OptimizedRecursiveSegmentTree(const std::vector<int> &v) noexcept
          : size(v.size()) {
          t.resize(4 * size);
          _build(v, 0, 0, size);
      }
  
      void add(unsigned i, int x) { _add(0, 0, size, i, x); }
  
      long long get(unsigned l, unsigned r) const {
          return _get(0, 0, size, l, r);
      }
  };
  

• Нерекурсивная реализация (взял отсюда: https://mirror.codeforces.com/blog/entry/18051)
  Код

  struct NonRecursiveSegmentTree {
      unsigned size;
  
    private:
      std::vector<long long> t;
  
      void _build(const std::vector<int> &v) {
          std::copy(v.begin(), v.end(), t.begin() + size);
          for (int i = size - 1; i > 0; --i) {
              t[i] = t[i * 2] + t[i * 2 ^ 1];
          }
      }
  
    public:
      NonRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {
          t.resize(2 * size);
      }
  
      NonRecursiveSegmentTree(const std::vector<int> &v) noexcept
          : size(v.size()) {
          t.resize(2 * size);
          _build(v);
      }
  
      void add(unsigned i, int x) {
          i += size;
          for (t[i] += x; i > 1; i /= 2) {
              t[i / 2] = t[i] + t[i ^ 1];
          }
      }
  
      long long get(unsigned l, unsigned r) const {
          long long res = 0;
          for (l += size, r += size; l < r; l /= 2, r /= 2) {
              if (l & 1) {
                  res += t[l++];
              }
              if (r & 1) {
                  res += t[--r];
              }
          }
          return res;
      }
  };
  

• Дерево Фенвика
  Код

  struct FenwickTree {
      unsigned size;
  
    private:
      std::vector<long long> t;
  
      long long get_prefix(int i) const {
          long long res = 0;
          while (i >= 0) {
              res += t[i];
              i = (i & (i + 1)) - 1;
          }
          return res;
      }
  
    public:
      void add(unsigned i, int x) {
          while (i < size) {
              t[i] += x;
              i = i | (i + 1);
          }
      }
  
      FenwickTree(unsigned _size) : size(_size) { t.resize(size); }
  
      FenwickTree(const std::vector<int> &v) : size(v.size()) {
          t.resize(size);
          for (unsigned i = 0; i < size; ++i) {
              add(i, v[i]);
          }
      }
  
      long long get(unsigned l, unsigned r) {
          return get_prefix((int)r - 1) - get_prefix((int)l - 1);
      }
  };
  

Все реализации поддерживают такие запросы:

• get(l, r): сумма на отрезке (полуинтервале) $$$[l; r)$$$
• add(i, x): прибавление к элементу под индексом $$$i$$$ числа $$$x$$$

Вот результаты:

Примечание: я старался не делать никаких оптимизаций, требовательных к конкретным запросам, чтобы с небольшими изменениями структуры данных могли применяться для любых операций.

Я генерировал запросы следующим образом:

• Прибавление в точке: случайный индекс (rnd() % size) и случайное число
• Сумма на отрезке: сначала, генерируется длина отрезка (rnd() % size + 1), затем подходящая левая граница.

Исходники бенчмарка. Примечание: желательно отключить CPU frequency scaling, закрыть все приложения, которые могут мешать бенчмарку (чем больше закроете -- тем в теории стабильнее будет результат) и "прибить" процесс к конкретному CPU.

Скрипт на Python, создающий красивый график

Результаты в формате JSON на случай, если Вы захотите ещё поиграться с данными.

Я компилировал бенчмарк с #pragma GCC optimize("O3") на GNU GCC 11.3.0, запускал его с фиксированной частотой процессора 2.4 GHz, прикрепив к конкретному ядру процессора.

Наверное, это мой первый вклад в сообщество, поэтому любые дополнения/предложения приветствуются.