Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- template<typename T_Type, typename Function, typename Multiple_Function>
- class LazySegmentTree {
- struct TreeNode;
- typedef std::unique_ptr<TreeNode> uniqueNodePtr_;
- typedef TreeNode *nodePtr_;
- struct TreeNode {
- T_Type val_;
- bool has_changed_;
- uniqueNodePtr_ left_;
- uniqueNodePtr_ right_;
- TreeNode(T_Type val, bool has_changed = true) : val_(val), has_changed_(has_changed), left_(
- nullptr), right_(nullptr) {
- }
- };
- private:
- uniqueNodePtr_ root_;
- size_t real_size_;
- T_Type default_val_;
- Function func_;
- Multiple_Function multiple_func_;
- inline void push(nodePtr_ node) {
- if (node->has_changed_) {
- if (node->left_ == nullptr) {
- node->left_ = uniqueNodePtr_(new TreeNode(node->val_, true));
- node->right_ = uniqueNodePtr_(new TreeNode(node->val_, true));
- } else {
- node->left_->val_ = node->right_->val_ = node->val_;
- node->left_->has_changed_ = node->right_->has_changed_ = true;
- }
- node->has_changed_ = false;
- }
- }
- inline T_Type getData(nodePtr_ node, size_t left, size_t right) const {
- if (node->has_changed_) {
- return multiple_func_(node->val_, right - left);
- } else {
- return node->val_;
- }
- }
- // makes a change from the position "from" to the position "to"
- // STL style: [left, right), [from, to)
- inline void setRecursive(nodePtr_ node, size_t left, size_t right, size_t from, size_t to,
- T_Type val) {
- if (from >= right || left >= to) {
- return;
- }
- if (left == from && right == to) {
- node->val_ = val;
- node->has_changed_ = true;
- } else {
- push(node);
- size_t mid = (left + right) / 2;
- setRecursive(node->left_.get(), left, mid, from, std::min(to, mid), val);
- setRecursive(node->right_.get(), mid, right, std::max(from, mid), to, val);
- node->val_ = func_(getData(node->left_.get(), left, mid),
- getData(node->right_.get(), mid, right));
- }
- }
- inline const T_Type getRecursive(nodePtr_ node, size_t left, size_t right, size_t from,
- size_t to) {
- if (from >= right || left >= to) {
- return default_val_;
- }
- if (left == from && right == to) {
- return getData(node, left, right);
- } else {
- push(node);
- size_t mid = (left + right) / 2;
- T_Type left_ans = getRecursive(node->left_.get(), left, mid, from, std::min(to, mid));
- T_Type right_ans = getRecursive(node->right_.get(), mid, right, std::max(from, mid),
- to);
- node->val_ = func_(getData(node->left_.get(), left, mid),
- getData(node->right_.get(), mid, right));
- return func_(left_ans, right_ans);
- }
- }
- public:
- LazySegmentTree(const std::vector<T_Type> &data, T_Type default_val = T_Type(0), Function func = Function(),
- Multiple_Function multiple_func = Multiple_Function()) :
- root_(uniqueNodePtr_(new TreeNode(default_val))), real_size_(data.size()),
- default_val_(default_val), func_(func), multiple_func_(multiple_func) {
- for (size_t i = 0; i < real_size_; ++i) {
- set(i, data[i]);
- }
- }
- inline void set(size_t left, size_t right, T_Type val) {
- setRecursive(root_.get(), 0, real_size_, left, right, val);
- }
- inline void set(size_t pos, T_Type val) {
- set(pos, pos + 1, val);
- }
- inline const T_Type get(size_t left, size_t right) {
- return getRecursive(root_.get(), 0, real_size_, left, right);
- }
- inline const T_Type get(size_t pos) {
- return get(pos, pos + 1);
- }
- inline const T_Type get() {
- return get(0, real_size_);
- }
- };
- template<typename T_Type>
- struct TwoVarSum {
- inline T_Type operator()(const T_Type &lhs, const T_Type &rhs) const {
- return lhs + rhs;
- }
- };
- LazySegmentTree<int, TwoVarSum<int>, std::multiplies<int>> tree({5, 7, 3});
- std::cout << tree.get(0, 2) << std::endl;
- return 0;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement