# 56ms BST C++ solution

• Everyone is sharing Segment Tree or BIT solutions.
BST is just another way to solve it.

``````struct MyTreeNode {
int index;
int val;
int less;
MyTreeNode* left;
MyTreeNode* right;
};

class NumArray {
public:
NumArray(vector<int> &nums) {
int sum = 0;
tree = buildTree(nums, 0, nums.size(), sum);
}

void update(int i, int val) {
int oldValue = addValue(i, val);
addValue(i, -oldValue);
}

int sumRange(int i, int j) {
return getLessThanIndex(j + 1) - getLessThanIndex(i);
}
private:
MyTreeNode* tree;
MyTreeNode* buildTree(vector<int>& nums, int begin, int end, int& sum) {
if (begin == end) return nullptr;

int mid = begin + (end - begin) / 2;
auto root = new MyTreeNode();
int leftSum = 0, rightSum = 0;
root->left = buildTree(nums, begin, mid, leftSum);
root->right = buildTree(nums, mid + 1, end, rightSum);
root->index = mid;
root->less = leftSum;
root->val = nums[mid];
sum = leftSum + rightSum + root->val;
return root;
}

int addValue(int i, int val) {
int oldValue = 0;
auto p = tree;
while (p) {
if (p->index == i) {
oldValue = p->val;
p->val += val;
break;
} else if (p->index > i) {
p->less += val;
p = p->left;
} else {
p = p->right;
}
}
return oldValue;
}

int getLessThanIndex(int i) {
int sum = 0;
auto p = tree;
while (p) {
if (p->index == i) {
sum += p->less;
break;
} else if (p->index > i) {
p = p->left;
} else {
sum += p->less + p->val;
p = p->right;
}
}
return sum;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.