# PBinfo #3886 – Suma intervale – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se citesc de la tastură două numere naturale n și m, apoi un șir de n numere naturale. Asupra șirului de numere se pot aplica m operații de două feluri: modificarea unei valori din șir și respectiv determinarea sumei valorilor din șir aflate între două poziții date.

Date de intrare
Programul citește de la tastatură două numere naturale n și m și cele n numere naturale ale șirului, separate prin spații. Apoi se citesc cele m operații care se vor aplica șirului de valori. Pentru fiecare operație se citesc trei valori op, x, y cu următoarea semnificație: 


dacă op=1 atunci se va modifica valoarea de la poziția x din șir cu valoarea y;
dacă op=2 atunci se va afișa suma valorilor din șir aflate între poziția x și y;

Date de ieșire
Programul va afișa pe ecran pe fiecare linie o valoare S, reprezentând suma valorilor de la operațiile de tipul 2.

Restricții și precizări

1 ≤ n, m ≤ 100.000
cele n numere din șirul de valori vor fi mai mici decât 1.000.000.000
numerotarea pozițiilor în șir va începe de la 1
1 ≤ x ≤ y ≤ n

Exemplu:
Intrare

5 5
1 2 3 4 5
2 1 5
1 3 4
2 1 5
1 4 10
2 3 5
Ieșire

15
16
19

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
long long a[100001];
long long seg[400001];
void arbore(int i, int left, int right)
{
    if(left==right)
    {
        seg[i]=a[left];
    }
    else
    {
        int mij=(left+right)/2;
        arbore(i*2,left,mij);
        arbore(i*2+1,mij+1,right);
        seg[i]=seg[2*i]+seg[2*i+1];
    }
}
long long suma(int i, int left, int right, int ls, int rd)
{
    if(ls<=left && rd>=right)
        return seg[i];
    else
        if (ls>right || rd<left) return 0;
    else
    {
       int mij=(left+right)/2;
        long long l=suma(2*i,left,mij,ls,rd);
        long long r=suma(2*i+1,mij+1,right,ls,rd);
        return l+r;
    }
}
void modifica(int i, int left, int right, int ls)
{
    if(left==right)seg[i]=a[left];
    else
    {
        int mij=(left+right)/2;
        if(ls<=mij) modifica(2*i,left,mij,ls);
        else modifica(2*i+1,mij+1,right,ls);
        seg[i]=seg[2*i]+seg[2*i+1];
    }
}
int main()
{ int n,i,m,ls,rd,op;
  cin>>n>>m;
  for(i=1;i<=n;i++)
    cin>>a[i];
  arbore(1,1,n);
  //for(i=1;i<=2*n-1;i++)
   // cout<<seg[i]<<" ";cout<<endl;
  for(i=1;i<=m;i++)
  {
      cin>>op>>ls>>rd;
      if(op==2)
      cout<<suma(1,1,n,ls,rd)<<'\n';
      else
      {
          a[ls]=rd;
          modifica(1,1,n,ls);
      }
  }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3886)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3886/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3886/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)