线段树

class segmentTree
{
public:
	void buildTree(int parr[], int root, int start, int end)// parr[]:待处理数组，root:根节点下标,start区间开始，end:区间结束；
	{
		if (start == end)
		{
			treeArr[root] = parr[start];
			return;
		}
		int mid = (start + end) / 2;
		int left = 2 * root + 1, right = 2 * root + 2;
		buildTree(parr, left, start, mid);
		buildTree(parr, right, mid + 1, end);
		treeArr[root] = treeArr[left] + treeArr[right];
	}
	void updata(int index, int val) {
		updata(root, start, end, index, val);
	}
	void updata(int root, int start, int end, int index, int val)
	{
		if (start == end)
		{
			treeArr[root] = val;
			return;
		}
		int mid = (start + end) / 2;
		int left = 2 * root + 1, right = 2 * root + 2;
		if (index <= mid)
			updata(left, start, mid, index, val);
		else
			updata(right, mid + 1, end, index, val);
		treeArr[root] = treeArr[left] + treeArr[right];
	}
	int getSum(int left, int right)const
	{
		return getSum(root, start, end, left, right);
	}
	int getSum(int root, int start, int end, int left, int right)const
	{
		if (end < left || start > right)
			return 0;
		else if (end <= right && start >= left)
			return treeArr[root];
		int mid = (start + end) / 2;
		int left_root = 2 * root + 1, right_root = 2 * root + 2;
		int sum_l = getSum(left_root, start, mid, left, right);
		int sum_r = getSum(right_root, mid + 1, end, left, right);
		return sum_l + sum_r;
	}
	segmentTree() {};
	segmentTree(int parr[], int n) {
		flag = 1;
		end = n - 1;
		treeArr = new int[4 * (n + 1)];
		buildTree(parr, root, start, end);
	}
	~segmentTree() {
		if (flag)
			delete treeArr;
	}
private:
	int* treeArr;
	int root = 0, start = 0, end;
	int flag = 0;
};

线段树

原文：https://www.cnblogs.com/youseecode/p/14613168.html