欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C数据结构-线段树

程序员文章站 2022-07-13 13:31:42
...

leetcode307题,区域和检索 - 数组可修改。
作者大牛,讲的特别好https://www.bilibili.com/video/av47331849/

题目需求分为三个部分
1、提供一个数组arr/nums–构造线段树node
2、更新数组的值–更新线段树
3、对某个区间求和–对线段树进行求和

线段树的好处是,保证更新和求和的时间是logn,均匀的。
线段树的特征是:
1、arr的值存在最底下
2、当前节点是值是左右孩子的和
3、node[0]存arr的范围是0到5的部分;
4、node[20+1]存arr的范围是0到(0+5)/2的部分
5、node[2
0+2]存arr的范围是(0+5)/2 + 1到5的部分
node之间的关系是left = 2 * nodeIndex + 1,right= 2 * nodeIndex + 2;
arr之间的关系是左边 (start, mid),(mid + 1, end)

所以nodeindex,start,end非常重要,可以确定当前的映射关系
所以一定要从nodeindex=0开始

大牛这个图画的挺好,我就不再创造加工了
C数据结构-线段树

1、建立

void build(NumArray* obj, int *nums, int nodeIndex, int start, int end) {
	if (start == end) {
		obj->node[nodeIndex] = nums[start];
		if (nodeIndex + 1 > obj->nodeSize) {
			obj->nodeSize = nodeIndex + 1;
		}
		return;
	}
	int mid = (start + end) / 2;
	int left = 2 * nodeIndex + 1;
	int right = 2 * nodeIndex + 2;
	build(obj, nums, 2 * nodeIndex + 1, start, mid);
	build(obj, nums, 2 * nodeIndex + 2, mid + 1, end);
	obj->node[nodeIndex] = obj->node[left] + obj->node[right];
	return;
}

NumArray* numArrayCreate(int* nums, int numsSize) {
	if (numsSize == 0) {
		return NULL;
	}
	NumArray *obj = (NumArray *)malloc(sizeof(NumArray));
	obj->nodeSize = 0;
	obj->numSize = numsSize;
	build(obj, nums, 0, 0, numsSize - 1);
	return obj;

}

2、 更新

void update(NumArray* obj, int i, int target, int nodeIndex, int start, int end) {
	if (start == end) {
		obj->node[nodeIndex] = target;
		return;
	}
	int mid = (start + end) / 2;
	int left = 2 * nodeIndex + 1;
	int right = 2 * nodeIndex + 2;
	if (i <= mid) {
		update(obj, i, target, left, start, mid);
	}
	else {
		update(obj, i, target, right, mid + 1, end);
	}
	obj->node[nodeIndex] = obj->node[left] + obj->node[right];
	return;
}

void numArrayUpdate(NumArray* obj, int i, int val) {
	update(obj, i, val, 0, 0, obj->numSize - 1);
}

3、求和

int funcSum(NumArray* obj, int L, int R, int nodeIndex, int start, int end) {
	//printf("start = %d end = %d,  L =%d  R= %d\n", start, end, L ,R);
	if (R<start || L>end) {
		return 0;
	}
	else if (L <= start && R >= end) {
		return  obj->node[nodeIndex];
	}
	int mid = (start + end) / 2;
	int left = 2 * nodeIndex + 1;
	int right = 2 * nodeIndex + 2;
	return funcSum(obj, L, R, left, start, mid) + funcSum(obj, L, R, right, mid + 1, end);
}

int numArraySumRange(NumArray* obj, int i, int j) {
	return funcSum(obj, i, j, 0, 0, obj->numSize - 1);
}

4、其他补充

typedef struct {
	int nodeSize;
	int numSize;
	int node[MAXLEN];
} NumArray;
void numArrayFree(NumArray* obj) {
	free(obj);
}

相关标签: C