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

全栈程序员-用户IM • 2022年8月30日上午7:16 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

例如: 给你任意几个数,给定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;
}