SegmentTree.h

Go to the documentation of this file.

#ifndef   dsa_SegmentTree_H__
#define   dsa_SegmentTree_H__

#include "../math/utility.h"

#include <vector>
#include <algorithm>

#include <cstdlib>

namespace meow {
template<class Value>
class SegmentTree {
private:
  struct Node {
    Value     value_;
    Value    offset_;
    bool  sameFlage_;
  };
  //
  size_t             size_;
  std::vector<Node> nodes_;
  //
  void update(size_t index, size_t size, Value const& value, bool override) {
    if (override) {
      nodes_[index].value_    = value * size;
      nodes_[index].offset_   = value;
      nodes_[index].sameFlage_ = true;
    }
    else {
      nodes_[index].value_  = nodes_[index].value_  + value * size;
      nodes_[index].offset_ = nodes_[index].offset_ + value;
    }
  }
  void update(size_t l, size_t r, size_t L, size_t R,
              size_t index, Value const& value,
              bool override) {
    if (l == L && r == R) {
      update(index, R - L + 1, value, override);
      return ;
    }
    size_t mid = (L + R) / 2;
    if (L < R) {
      update(index * 2 + 1, mid - L + 1,
             nodes_[index].offset_, nodes_[index].sameFlage_);
      update(index * 2 + 2, R - mid,
             nodes_[index].offset_, nodes_[index].sameFlage_);
      nodes_[index].offset_ = Value(0);
      nodes_[index].sameFlage_ = false;
    }
    if (r <= mid) {
      update(l, r, L ,mid, index * 2 + 1, value, override);
    }
    else if (mid + 1 <= l) {
      update(l, r, mid + 1,R, index*2 + 2, value, override);
    }
    else {
      update(l, mid       , L, mid       , index * 2 + 1, value, override);
      update(   mid + 1, r,    mid + 1, R, index * 2 + 2, value, override);
    }
    nodes_[index].value_ = (
      (nodes_[index * 2 + 1].value_ | nodes_[index * 2 + 2].value_)
      + nodes_[index].offset_
    );
  }
  Value query(size_t l, size_t r, size_t L, size_t R, size_t index) {
    if (l == L && r == R) return nodes_[index].value_;
    Value off = nodes_[index].offset_ * (r - l + 1);
    if (nodes_[index].sameFlage_) return off;
    size_t mid = (L + R) / 2;
    if     (r       <= mid) return query(l, r, L   ,  mid, index * 2 + 1) + off;
    else if(mid + 1 <=   l) return query(l, r, mid + 1, R, index * 2 + 2) + off;
    else{
      return (  query(l, mid       , L,  mid       , index * 2 + 1)
              | query(   mid + 1, r,     mid + 1, R, index * 2 + 2)
      ) + off;
    }
  }
  //
  bool rangeCorrect(ssize_t* first, ssize_t* last) const {
    if (*last < *first || *last < 0 || (ssize_t)size_ - 1 < *first)
      return false;
    *first = inRange((ssize_t)0, (ssize_t)size_ - 1, *first);
    *last  = inRange((ssize_t)0, (ssize_t)size_ - 1, *last );
    return true;
  }
public:
  SegmentTree() {
    reset(1);
  }

  SegmentTree(size_t size) {
    reset(size);
  }

  SegmentTree(SegmentTree const& tree2):
  size_(tree2.size_), nodes_(tree2.nodes_) {
  }

  SegmentTree copyFrom(SegmentTree const& b) {
    size_  = b.size_;
    nodes_ = b.nodes_;
    return *this;
  }

  size_t size() const {
    return size_;
  }

  void reset(size_t size){
    size_ = std::max(size, (size_t)1);
    nodes_.resize(size * 4);
    nodes_[0].sameFlage_ = true;
    nodes_[0].value_  = Value(0);
    nodes_[0].offset_ = Value(0);
  }

  Value query(ssize_t first, ssize_t last) const {
    if (rangeCorrect(&first, &last) == false) return Value();
    return ((SegmentTree*)this)->query(first, last, 0, size_ - 1, 0);
  }

  void override(ssize_t first, ssize_t last, Value const& value) {
    if (rangeCorrect(&first, &last) == false) return ;
    update(first, last, 0, size_ - 1, 0, value, true);
  }

  void offset(ssize_t first, ssize_t last, Value const& delta) {
    if (rangeCorrect(&first, &last) == false) return ;
    update(first, last, 0, size_ - 1, 0, delta, false);
  }

  SegmentTree& operator=(SegmentTree const& b) {
    return copyFrom(b);
  }
};

}

#endif // dsa_SegmentTree_H__