Дерево фенвика

(просто для разминки)

template <typename T = int>
class Summator {

 public:
  Summator(size_t size)
    : vector_(size + 1)
  { }

  void add(size_t index, const T& value)
  {
    for (++index; index < vector_.size(); index = next(index))
      vector_[index] += value;
  }

  T sum(size_t index) const
  {
    T result = 0;
    for (++index; index; index = prev(index))
      result += vector_[index];
    return result;
  }

 private:
  static size_t prev(size_t index)
  {
    return index & (index - 1);
  }

  static size_t next(size_t index)
  {
    return index + index - prev(index);
  }

  std::vector<T> vector_;
};