dalao求跳,有赏,私信
查看原帖
dalao求跳,有赏,私信
502983
jhhh楼主2024/9/7 17:01
#include<bits/stdc++.h>
using namespace std;
struct node { //定义一个块,用来存数据
	int num;//该块的值的和
	int ll,rr;//存储我的下标
	node *l,*r;//左子块,右子块
};
node *temp;//临时指针,用来记录我的一个子节点
//建树
bool build(int listt[],int l,int r) { //该序列的数组,左下标,右下标
//	if(l>r)return 0;
	if(l==r) {
		node* t=new(node);//建立一个新节点
		t->num=listt[l];
		t->ll=l;
		t->rr=r;
		t->l=NULL;
		t->r=NULL;
		temp=t;
		return 1;
	}
	node* me=new(node);//建立一个块,是我自己,因为我们区间不会重复选中
	me->num=0;
	me->ll=l;
	me->rr=r;
	int mid=(l+r)/2;//取中间值,划分成两个区间
	if(build(listt,l,mid)) {
		me->l=temp;
		me->num+=temp->num;
	}
	if(build(listt,mid+1,r)) {
		me->r=temp;
		me->num+=temp->num;
	}
	temp=me;
	return 1;
}
void tree_add(node* tree,int l,int r,int k) { //在某个范围添加值
	printf("%d %d\n",tree->ll,tree->rr); 
	if(tree->ll>tree->rr)return;
	//判断范围,烦
	//l,r是需要操作的区间,如果我不在区间内,不管
	int my_l=tree->ll,my_r=tree->rr;
	//如果我不在区间内
	if(my_l>r||my_r<l)return;
	//左子树在区间内
	int my_sonl,my_sonr;
	if(tree->l!=NULL) {
		my_sonl=tree->l->ll,my_sonr=tree->l->rr;
		if(!(my_sonl>r||my_sonr<l))tree_add(tree->l,l,r,k);
	}
	//右子树在区间内
	if(tree->r!=NULL) {
		my_sonl=tree->r->ll,my_sonr=tree->r->rr;
		if(!(my_sonl>r||my_sonr<l))tree_add(tree->r,l,r,k);
	}
	//我自己加
	tree->num+=(r-l+1)*k;
	return;
}
int tree_query(node* tree,int l,int r) {
	if(l>r)return 0;
	int my_l=tree->ll,my_r=tree->rr;//l,r是需要操作的区间,如果我不在区间内,不管
	if(my_l>r||my_r<l)return 0;
	if(my_l==l&&my_r==r)return tree->num;//我恰好是要找的
	int sum=0;
	//l r是要查询的区间
	//先判断左子树
	int son_l,son_r;
	if(tree->l!=NULL) {
		son_l=tree->l->ll,son_r=tree->l->rr;
		if(l<=son_r) {
			if(r<=son_r) { //整体在本区间内
				sum+=tree_query(tree->l,l,r);
			} else {
				sum+=tree_query(tree->l,l,son_r);
			}
		}
	}
	if(tree->r!=NULL) {
		son_l=tree->r->ll,son_r=tree->r->rr;
		if(r>=son_l) {
			if(l>=son_l) { //整体在本区间内
				sum+=tree_query(tree->r,l,r);
			} else {
				sum+=tree_query(tree->r,son_l,r);
			}
		}
	}
	return sum;
}
int main() {
//	freopen(".out","w",stdout);
	int a[20];
	for(int i=1;i<=5;i++){
		cin>>a[i];
	}
	build(a,1,5);
	tree_add(temp,1,2,1);
	node* t=temp;
	cout<<t->l->l->l->num<<endl;
	return 0;
}
2024/9/7 17:01
加载中...