diff options
author | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-21 14:13:53 +0800 |
---|---|---|
committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-21 14:13:53 +0800 |
commit | 1817d739e89b1d4c1c09d5f553ce5068fab0e4d7 (patch) | |
tree | a2c19c84b45a7b814cff17df4ed952b47b50a49b /meowpp/dsa/SegmentTree.h | |
parent | 309e100b5d4200bec36d08e4882d62a80df262e6 (diff) | |
download | meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.tar meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.tar.gz meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.tar.bz2 meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.tar.lz meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.tar.xz meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.tar.zst meow-1817d739e89b1d4c1c09d5f553ce5068fab0e4d7.zip |
壓力測試完成~~~~~~~~~~
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 |