满二叉树的线段树代码,C代码库,德仔网

代码语言

代码分类

【C】满二叉树的线段树

作者:dongdongzhang_ / 发布于2013/10/23/ 699


	#include <stdio.h>
	#include <math.h>
	#include <stdlib.h>
	#include <string.h>
	//完全二叉树 线段树
	int main() {
	int T;
	scanf("%d", &T);
	for(int j = 1; j <= T; ++j) {
	 int N;
	 scanf("%d", &N);
	 int deepth = (int) (log(2.0 * N) / log(2.0)) + 1; //树的深度
	 int *p = (int *) malloc(sizeof(int) * (int) pow(2.0, deepth));
	 int index = (int) pow(2.0, deepth-1); //叶节点的首位置
	 memset(p, 0, sizeof(int) * (int) pow(2.0, deepth)); //初始化为0
	 for(int i = 0; i < N; ++i)
	 scanf("%d", p + index + i);
	 //从最后一个根节点，到第一个根节点
	 for(int i = index - 1; i >= 1; i--)
	 *(p + i) = *(p + 2 * i) + *(p + 2 * i + 1);
	 printf("Case %d:n", j);
	 char ch[10];
	 while(scanf("%s", ch) && strcmp(ch, "End")) {
	 int a, b;
	 scanf("%d%d", &a, &b);
	 int temp_index = index + a - 1;
	 if(strlen(ch) == 5) {
	 int total = 0;
	 while(a <= b) {
	 int temp = 1;
	 //寻找所属的区域
	 while(temp_index % (2 * temp) == 0 && a + 2 * temp - 1 <= b)
	 temp *= 2;
	 total += *(p + temp_index / temp); //找到全属区域最大的根节点
	 a += temp;
	 temp_index += temp;
	 }
	 printf("%dn", total);
	 }
	 else {
	 if(!strcmp(ch, "Sub"))
	 b = -b;
	 while(temp_index) {
	 *(p + temp_index) += b;
	 temp_index /= 2;
	 }
	 }
	 }
	}
	}

试试其它关键字

　二叉树　

同语言下

可能有用的

dongdongzhang_贡献的其它代码(1)

.满二叉树的线段树