简单线段树模板[通俗易懂]

大家好，又见面了，我是你们的朋友全栈

例如: 给你任意几个数,给定N个区间,让你求这个区间的和;简单线段树的运用,帮助我更好的理解线段树,

//线段树基本 #include<stdio.h> #define MAXN 100100 #define MINN 10000100 int num[MAXN],t[MINN]; void build(int L,int R,int d) { if(L==R) { t[d]=num[L]; return ; } else { int mid=(L+R)/2; build(L,mid,d*2); build(mid+1,R,2*d+1); } t[d]=t[2*d]+t[2*d+1];//回溯很重要容易漏 } int inqure(int L,int R,int cl,int cr,int d) { if(L==cl&&R==cr) { return t[d]; } else { int mid=(L+R)/2; if(cr<=mid) return inqure(L,mid,cl,cr,d*2); else if(cl>mid) return inqure(mid+1,R,cl,cr,d*2+1); else { return inqure(L,mid,cl,mid,d*2)+inqure(mid+1,R,mid+1,cr,d*2+1);//查找时候的判断分为三种情况,全在左面就左查,右面就右查,左右都有就两个都查然后相加; } } } int main() { int t,n,i,l,r,q; scanf(“%d”,&t); while(t–) { scanf(“%d”,&n); for(i=1;i<=n;i++) { scanf(“%d”,&num[i]); } build(1,n,1);//从父结点开始建立// scanf(“%d”,&q); for(i=1;i<=q;i++) { scanf(“%d %d”,&l,&r); int sum=inqure(1,n,l,r,1);//从树根开始查找; printf(“%d\n”,sum); } } return 0; }

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/178798.html原文链接：https://javaforall.cn