diff options
Diffstat (limited to 'meowpp/dsa/SegmentTree.h')
| -rw-r--r-- | meowpp/dsa/SegmentTree.h | 49 |
1 files changed, 31 insertions, 18 deletions
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h index 1aa396d..585ea5d 100644 --- a/meowpp/dsa/SegmentTree.h +++ b/meowpp/dsa/SegmentTree.h @@ -9,27 +9,19 @@ namespace meow{ Value _value; Value _offset; bool _sameFlag; - // - Node(); }; // size_t _size; std::vector<Node> _nodes; - size_t const _root; // - size_t leftChild(size_t __parent) const; - size_t rightChild(size_t __parent) const; - // - void downUpdate(size_t __L, size_t __R, size_t __index); - void override(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index, Value const& __value); - void offset(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index, Value const& __delta); - Value query(size_t __l, size_t __r, - size_t __L, size_t __R, + void update(size_t __index, size_t __size, Value const& __value, + bool __override); + void update(size_t __l, size_t __r, size_t __L, size_t __R, + size_t __index, Value const& __value, + bool __override); + Value query(size_t __l, size_t __r, size_t __L, size_t __R, size_t __index); + // bool rangeCorrect(ssize_t* __first, ssize_t* __last) const; public: SegmentTree(); @@ -38,9 +30,28 @@ namespace meow{ // void reset(size_t __size); // - Value query (ssize_t __first, ssize_t __last) const; - void override(ssize_t __first, ssize_t __last, Value const& __value); - void offset (ssize_t __first, ssize_t __last, Value const& __delta); + Value query (ssize_t __first, ssize_t __last) const; + void override(ssize_t __first, ssize_t __last, Value const& __value); + void offset (ssize_t __first, ssize_t __last, Value const& __delta); + void print(){ + for(int i = 0; i < _size; i++){ + query(i, i); + } + printf("\n"); + for(int depth = 0, count = 1, size = _size, id = 0; + size > 0; + depth++, count *= 2, size /= 2){ + for(int j = 0; j < count; j++, id++){ + printf("[%3d%c%3d%*s]", + _nodes[id]._value.value, + _nodes[id]._sameFlag ? 's' : ' ', + _nodes[id]._offset.value, + size * 9 - 9, + ""); + } + printf("\n"); + } + } }; /********************************************************* @asciidoc @@ -89,4 +100,6 @@ namespace meow{ *********************************************************/ } +#include "SegmentTree.hpp" + #endif |