using System;

​

class FenwickTree

{

    private int[] BIT;

    private int n;

​

    public FenwickTree(int size)

    {

        n = size;

        BIT = new int[n + 1];  // BIT usa índices desde 1 hasta n

    }

​

    // Actualiza el BIT sumando `value` al índice `index`

    public void Update(int index, int value)

    {

        while (index <= n)

        {

            BIT[index] += value;

            index += index & -index;  // Suma el último bit significativo

        }

    }

​

    // Retorna la suma desde el índice 1 hasta `index`

    private int Query(int index)

    {

        int sum = 0;

        while (index > 0)

        {

            sum += BIT[index];

            index -= index & -index;  // Resta el último bit significativo

        }

        return sum;

    }

​

    // Retorna la suma en el rango [L, R]

    public int QueryRange(int L, int R)

    {

        return Query(R) - Query(L - 1);

    }

}

​

class Program

{

    static void Main()

    {

        int[] arr = { 1, 3, 5, 7, 9, 11 };

        int n = arr.Length;

        FenwickTree fenwick = new FenwickTree(n);

​

        // Construcción inicial del Árbol de Fenwick

        for (int i = 0; i < n; i++)

        {

            fenwick.Update(i + 1, arr[i]);  // BIT usa índices desde 1

        }

​

        Console.WriteLine("Suma en el rango [1, 4]: " + fenwick.QueryRange(1, 4));  // 1 + 3 + 5 + 7 = 16

​

        // Actualizar el valor en la posición 3 (índice 2 en C#)

        fenwick.Update(3, 1);  // Incrementamos arr[2] en 1 (5 → 6)

​

        Console.WriteLine("Suma en el rango [1, 4] después de la actualización: " + fenwick.QueryRange(1, 4));  // 1 + 3 + 6 + 7 = 17

    }

}

​