帮我用C++写一棵线段树
时间: 2023-03-13 08:32:59 浏览: 72
我可以帮你写一个C语言编写的线段树:#include <stdio.h>
#include <stdlib.h>typedef struct Node{
int left;
int right;
int max;
int lazy;
struct Node *leftChild;
struct Node *rightChild;
}Node;Node *createSegmentTree(int *arr, int n)
{
Node *root = (Node*)malloc(sizeof(Node));
root->left=0;
root->right=n-1;
root->max=arr[0];
root->lazy=0;
if(n==1)
{
root->leftChild=NULL;
root->rightChild=NULL;
}
else
{
root->leftChild=createSegmentTree(arr,n/2);
root->rightChild=createSegmentTree(arr+n/2,n-n/2);
}
return root;
}void update(Node *root,int l,int r,int val)
{
if(root->left>=l && root->right<=r)
{
root->lazy+=val;
root->max+=val;
return;
}
int mid=(root->left+root->right)/2;
if(l<=mid)
update(root->leftChild,l,r,val);
if(r>mid)
update(root->rightChild,l,r,val);
root->max=root->leftChild->max+root->rightChild->max+root->lazy;
}int query(Node *root,int l,int r)
{
if(root->left>=l && root->right<=r)
{
return root->max;
}
int mid=(root->left+root->right)/2;
int ans=root->lazy;
if(l<=mid)
ans+=query(root->leftChild,l,r);
if(r>mid)
ans+=query(root->rightChild,l,r);
return ans;
}int main()
{
int arr[10] = {2,4,3,1,6,7,8,9,1,7};
Node *root = createSegmentTree(arr,10);
update(root,3,4,10);
printf("Max=%d",query(root,2,6));
return 0;
}
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)