Últimammente he estado estudiando árboles de segmentos, y como estamos cerca del final del smeestre, mi estudio ha sido intermitente, lo que ha hecho que algunos conceptos no estén completamente claros. Sin embargo, entiendo que no puedo obsesionarme con los detalles, así que he combinado mi estudio con la resolución de problemas para profundizar mi comprensión.

A continuación, presento una implementación básica de árbol de segmentos para las operaciones más simples: actualización y consulta de rangos. Me he basado en una plantila de referencia y he simplificado el código utilizando macros:

 1 #include<cstdio>
 2 typedef long long LL;
 3 #define nodo  int nd, int izq, int der
 4 #define hijo_izq  nd*2, izq, medio
 5 #define hijo_der  nd*2+1, medio+1, der
 6 #definir_medio  int medio= (izq+der)>>1
 7 int inicio,fin;
 8 LL valor;
 9 
10 struct arbol {
11     LL agregar,suma;
12 } t[400003];
13 
14 void construir(nodo) {
15     t[nd].agregar= 0;
16     if(izq==der){
17         scanf("%lld",&t[nd].suma);
18         return ;
19     }
20     definir_medio;
21     construir(hijo_izq);
22     construir(hijo_der);
23     t[nd].suma= t[nd*2].suma+t[nd*2+1].suma;
24 }
25 
26 inline void propagar(int nd, int longitud) {
27     int izq_hijo= nd*2, der_hijo= izq_hijo+1;
28     const LL &c= t[nd].agregar;
29     t[izq_hijo].agregar += c;
30     t[der_hijo].agregar += c;
31     t[izq_hijo].suma += c*(longitud-longitud/2);
32     t[der_hijo].suma += c*(longitud/2);
33     t[nd].agregar= 0;
34 }
35 
36 void actualizar(nodo) {
37     if(inicio<=izq && der<=fin){
38         t[nd].agregar+= valor;
39         t[nd].suma+= valor*(der-izq+1);
40         return ;
41     }
42     if(t[nd].agregar)    propagar(nd,der-izq+1);
43     definir_medio;
44     if(inicio<=medio)    actualizar(hijo_izq);
45     if(fin>medio)    actualizar(hijo_der);
46     t[nd].suma= t[nd*2].suma+t[nd*2+1].suma;
47 }
48 
49 LL consultar(nodo) {
50     if(inicio<=izq && der<=fin)    return t[nd].suma;
51     if(t[nd].agregar)    propagar(nd,der-izq+1);
52     definir_medio;
53     LL resultado= 0;
54     if(inicio<=medio)    resultado+= consultar(hijo_izq);
55     if(fin>medio)    resultado+= consultar(hijo_der);
56     return resultado;
57 }
58 
59 int main(){
60     int n,q;
61     while(~scanf("%d%d",&n,&q)){
62         construir(1,1,n);
63         while(q--){
64             getchar();
65             if(getchar()=='Q'){
66                 scanf("%d%d",&inicio,&fin);
67                 printf("%lld\n",consultar(1,1,n));
68             }
69             else {
70                 scanf("%d%d%lld",&inicio,&fin,&valor);
71                 actualizar(1,1,n);
72             }
73         }
74     }
75     return 0;
76 }

La implementación original del código es:

 1 #include<cstdio>
 2 typedef long long LL;
 3 LL c;
 4 int a,b;
 5 
 6 struct arbol{
 7     LL add,sum;
 8 } s[400003];
 9 
10 void build(int rt, int l, int r){
11     s[rt].add= 0;
12     if(l==r){
13         scanf("%lld",&s[rt].sum);
14         return ;
15     }
16     int mid= (l+r)>>1;
17     build(rt*2,l,mid);
18     build(rt*2+1,mid+1,r);
19     s[rt].sum= s[rt*2].sum+s[rt*2+1].sum;
20 }
21 
22 inline void pushdown(int rt, int len){
23     if(s[rt].add){
24         int ls= rt*2, rs= ls+1;
25         s[ls].add += s[rt].add;
26         s[rs].add += s[rt].add;
27         s[ls].sum += s[rt].add*(len-len/2);
28         s[rs].sum += s[rt].add*(len/2);
29         s[rt].add= 0;
30     }
31 }
32 
33 void update(int rt, int l, int r){
34     if(a<=l && r<=b){
35         s[rt].add+= c;
36         s[rt].sum+= c*(r-l+1);
37         return ;
38     }
39     pushdown(rt,r-l+1);
40     int mid= (l+r)>>1;
41     if(a<=mid)    update(rt*2,l,mid);
42     if(b>mid)    update(rt*2+1,mid+1,r);
43     s[rt].sum= s[rt*2].sum+s[rt*2+1].sum;
44 }
45 
46 LL query(int rt, int l, int r){
47     if(a<=l && r<=b)    return s[rt].sum;
48     pushdown(rt,r-l+1);
49     int mid= (l+r)>>1;
50     LL res= 0;
51     if(a<=mid)    res+= query(rt*2,l,mid);
52     if(b>mid)    res+= query(rt*2+1,mid+1,r);
53     return res;
54 }
55 
56 int main(){
57     int n,q;
58     while(~scanf("%d%d",&n,&q)){
59         build(1,1,n);
60         while(q--){
61             getchar();
62             if(getchar()=='Q'){
63                 scanf("%d%d",&a,&b);
64                 printf("%lld\n",query(1,1,n));
65             }
66             else {
67                 scanf("%d%d%lld",&a,&b,&c);
68                 update(1,1,n);
69             }
70         }
71     }
72     return 0;
73 }

Ver Código Continuando mi aprendizaje de árboles de segmentos~~