fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 1000000
  4. int BIT[MAX+1] = {0};
  5. void makeBIT(int array[], int size)
  6. {
  7. 	int lenBIT = size + 1;
  8. 	int i;
  9. 	for (i = 1; i < lenBIT; ++i)
  10. 	{
  11. 		BIT[i] += array[i-1];
  12. 		int k = i;
  13. 		while (k < lenBIT)
  14. 		{
  15. 			k += (k & -k);
  16. 			BIT[k] += array[i-1];
  17. 		}
  18. 	}		
  19. }
  20. void increment(int value, int idx, int size, int BIT[])
  21. {
  22. 	int lenBIT = size + 1;
  23. 	int i = idx + 1;
  24. 	while (i < lenBIT)
  25. 	{
  26. 		BIT[i] += value;
  27. 		i += (i & -i);
  28. 	}
  29. }
  30. int query(int idx, int BIT[])
  31. {
  32. 	int i = idx + 1;
  33. 	int sum = 0;
  34. 	while (i)
  35. 	{
  36. 		sum += BIT[i];
  37. 		i -= (i & -i);
  38. 	}
  39. 	return sum;
  40. }		
  41. int main (void)
  42. {
  43. 	int array[] = {1, 2, 3, 4 , 5, 6};
  44. 	int i;
  45. 	makeBIT(array, 6);
  46. 	for (i = 1; i <= 6; ++i)
  47. 		printf ("%d\n", BIT[i]);
  48. 	printf ("Queries\n");
  49. 	for (i = 1; i < 7; ++i)
  50. 		printf ("%d\n", query(i, BIT));
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 6152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
3
3
10
5
11
Queries
3
6
10
15
21
21
https://ideone.com/9z6CCw
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!