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_; };
Мнения, высказанные здесь, отражают мои личные взгляды. И мнения и взгляды со временем могут меняться.
вторник, 2 августа 2011 г.
Дерево фенвика
(просто для разминки)
Подписаться на:
Комментарии к сообщению (Atom)
Комментариев нет:
Отправить комментарий