树状数组模板

2021-05-22 07:29

阅读：392

标签：+= ref www. size 下标 gets include ios ems

用树状数组，在存数据的时候下标应该是从1开始的；
再求区间的和的时候和前缀和一样开始的下标是要减一的；
toSum（int x）中再求前缀和的时候是倒着向前走的；

树状数组讲解：http://www.cnblogs.com/jinkun113/p/4725420.html ORZorzorz一看就明白了

 1 //树状数组修改值，求某区间的和
 2 #include  3 #include  4 #include 
 5 #include  6 #include  7 #include string>
 8 #include  9 #include 10 #define INF 0x3f3f3f3f
11 #define FRE() freopen("in.txt","r",stdin)
12 
13 using namespace std;
14 typedef long long ll;
15 const int maxn = 1e5 + 5;
16 int a[maxn],c[maxn];
17 int T,n;
18 
19 int lowbit(int x)
20 {
21     return x & -x;
22 }
23 
24 void upDate(int i, int x)
25 {
26     while(i  n)
27     {
28         c[i] += x;
29         i += lowbit(i)
30     }
31 }
32 
33 int toSum(int x)
34 {
35     int sum = 0;
36     while(x > 0)
37     {
38         sum += c[x];
39         x -= lowbit(x);
40     }
41     return sum;
42 }
43 
44 int getSum(int st,int en)
45 {
46     return toSum(en) - toSum(st - 1);
47 }
48 
49 
50 
51 
52 int main()
53 {
54     memset(a, 0, sizeof(a));
55     memset(c, 0, sizeof(c));
56     scanf("%d",&T);
57     while(T--)
58     {
59         scanf("%d",&n);
60         for(int i = 1; i )
61         {
62             scanf("%d",&a[i]);
63             upDate(i, a[i]);//修改i位置的值
64         }
65         int st,en;
66         scanf("%d%d",&st,&en);
67         printf("%d\n",getSum(st, en));//输出st到en之间的和
68     }
69     return 0;
70 }

树状数组模板

标签：+= ref www. size 下标 gets include ios ems

原文地址：https://www.cnblogs.com/sykline/p/9737828.html

上一篇：Java学习1：static 和 public 不能放在方法里面

下一篇：javaScript 对于全局对象对象的理解

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：树状数组模板
文章链接：http://soscw.com/index.php/essay/87968.html

亲，登录后才可以留言！

树状数组模板

评论

热门文章

推荐文章

最新文章

置顶文章