SegmentTree (node)

SegmentTree.cc

class SegmentTreeNode {
public:
  int start;
  int end;
  int sum;
  SegmentTreeNode *left;
  SegmentTreeNode *right;
  SegmentTreeNode(int start, int end, int val)
      : start(start), end(end), sum(val), left(nullptr), right(nullptr) {}
  SegmentTreeNode(int start, int end, int val, SegmentTreeNode *left,
                  SegmentTreeNode *right)
      : start(start), end(end), sum(val), left(left), right(right) {}
};

SegmentTreeNode *buildTree(int start, int end, int val) {
  if (start >= end)
    return new SegmentTreeNode(start, end, val);
  int mid = (start + end) >> 1;
  SegmentTreeNode *left = buildTree(start, mid, val);
  SegmentTreeNode *right = buildTree(mid + 1, end, val);
  return new SegmentTreeNode(start, end, left->sum + right->sum, left, right);
}

void updateTree(SegmentTreeNode *root, int index, int val) {
  if (root->start == root->end && root->end == index) {
    root->sum = val;
    return;
  }
  int mid = (root->start + root->end) >> 1;
  if (index <= mid)
    updateTree(root->left, index, val);
  else
    updateTree(root->right, index, val);
  root->sum = root->left->sum + root->right->sum;
}

int queryTree(SegmentTreeNode *root, int left, int right) {
  if (root->start == root->end && root->end == left)
    return root->sum;
  int mid = (root->start + root->end) >> 1;
  if (right <= mid)
    return queryTree(root->left, left, right);
  if (left > mid)
    return queryTree(root->right, left, right);
  return queryTree(root->left, left, mid) +
         queryTree(root->right, mid + 1, right);
}