Example: segment tree complexity
class SegmentTree{
public:
vector<int> segv;
int n;
SegmentTree(vector<int> &nums) {
if (!nums.size()) return ;
segv.assign(nums.size() * 4, 0);
n = nums.size();
build(nums, 1, 0, n - 1);
}
void build(vector<int> &nums, int v, int l, int r) {
if (l == r) segv[v] = nums[l];
else {
int mid = l + (r - l) / 2;
build(nums, v * 2, l, mid);
build(nums, v * 2 + 1, mid + 1, r);
segv[v] = segv[v * 2] + segv[v * 2 + 1];
}
}
int sumRange(int v, int l, int r, int a, int b) {
if (a > b) return 0;
if (l == a && r == b) return segv[v];
int mid = l + (r - l) / 2;
return sumRange(v * 2, l, mid, a, min(mid, b))
+ sumRange(v * 2 + 1, mid + 1, r, max(mid + 1, a), b);
}
void update(int v, int l, int r, int pos, int val) {
if (l == r) segv[v] = val;
else {
int mid = l + (r - l) / 2;
if (pos <= mid) update(v * 2, l, mid, pos, val);
else update(v * 2 + 1, mid + 1, r, pos, val);
segv[v] = segv[v * 2] + segv[v * 2 + 1];
}
}
int sumRange(int a, int b) {
return sumRange(1, 0, n - 1, a, b);
}
void update(int pos, int val) {
update(1, 0, n - 1, pos, val);
}
};